Online Beck--Fiala Down to Logarithmic Sparsity

技术摘要：在线 Beck–Fiala 问题降至对数稀疏度

问题陈述
本文研究了 Beck–Fiala 猜想，这是组合差异理论中的一个核心问题。该猜想指出，对于任何每个列最多有 $d$ 个非零项的二值矩阵 $A \in \{0, 1\}^{n \times T}$，都存在一个符号序列 $\varepsilon \in \{-1, 1\}^T$，使得差异 $\|A\varepsilon\|_\infty$ 被限制在 $O(\sqrt{d})$ 范围内。至关重要的是，该界限应独立于维度 $n$ 和 $T$。

虽然离线版本的该问题已取得了显著进展（例如 Bansal 和 Jiang 建立了当 $d \ge \log(T)^2$ 时的界限），但在线变体仍然更具挑战性。在在线设置中，向量 $a_1, \dots, a_T$ 是顺序揭示的，算法必须不可撤回地选择符号 $\varepsilon_t$，以最小化前缀差异 $\max_{t \le T} \|\sum_{s=1}^t \varepsilon_s a_s\|_\infty$。在此工作之前，已知的最优在线 Beck–Fiala 算法界限为 $O(\sqrt{d \log T})$，该界限源自通用的 Komlós 结果。

方法论
作者开发了一种基于**紧支撑 Metropolis 固定点行走（compactly supported Metropolis fixed-point walk）**的高效随机在线算法。其核心方法论包含三个组成部分：

1. 三元耦合（Triplet Coupling）： 算法维护三个在有界定义域 $(-L, L)^n$ 内演化的耦合随机行走 $(X_{t,1}, X_{t,2}, X_{t,3})$。在每一步中，算法使用一种三路耦合引理（改编自 Aden-Ali）来为每个行走采样增量 $\delta_{t,j} \in \{-1, 0, 1\}$，使得它们的总和 $\varepsilon_t = \sum \delta_{t,j}$ 是一个真正的符号 $\{-1, 1\}$。
2. 平稳测度与平衡： 这些行走被设计为相对于特定的乘积测度 $\mu = \rho^{\otimes n}$ 是平稳的。算法确保当前状态 $X_{t-1}$ 相对于输入的向量 $v_t$ 是“平衡”的。如果一个状态是 $v$-平衡的，则向 $v$ 方向或 $-v$ 方向移动的概率足够高（具体而言，$p^+_v + p^-_v \ge 1/3$）。如果状态是平衡的，耦合过程将确保增量之和抵消漂移，从而使前缀和保持有界。
3. 尺度敏感曲率与凸峰密度（Bump Densities）： 为了处理稀疏向量（即 $d$ 较小时），作者构造了一个特定的不变密度 $\rho$（一种“凸峰律”），其支撑集在 $(-1, 1)$ 上。该密度通过势函数 $\Phi_\beta(y) = e^{(1-y^2)^{-\beta}}$ 定义。证明依赖于对该势函数曲率的分析。他们证明了对于稀疏向量，其“曲率尾部”（即势函数发生剧烈变化的概率）是指数级微小的。这使得能够界定行走变得不平衡的概率。

主要贡献与结果

• 定理 1.1 (在线 Beck–Fiala)： 作者提出了一种随机在线算法，在稀疏参数 $d$ 满足 $d \ge C (\log T)(\log \log T)^{2+\eta}$ 的情况下，可实现 $O(\sqrt{d})$ 的前缀差异。

  • 失败概率被限制在 $C_\eta T \exp\left(-\frac{c_\eta d}{\log^{2+\eta}(ed)}\right)$。
  • 这有效地将 Beck–Fiala 猜想的适用范围扩展到了近对数稀疏度区间，相比于此前离线结果的 $d \ge \log(T)^2$ 阈值以及在线结果的 $O(\sqrt{d \log T})$ 界限，这是一个显著的改进。

• 推论 1.2 (离线 Beck–Fiala)： 作为直接结果，本文确立了对于列稀疏度 $d$ 在相同对数区间内的矩阵的离线 Beck–Fiala 猜想。

• 推论 1.3 (在线 Spencer 前缀问题)： 该结果解决了 Spencer 设置下（其中向量属于 $[-1, 1]^n$）的在线向量平衡开放问题。作者证明，对于 $T \le \exp\left(\frac{c_\eta n}{\log^{2+\eta}(en)}\right)$，存在一种在线算法可实现 $O(\sqrt{n})$ 的前缀差异。这以强形式证实了 Kulkarni, Reis, 和 Rothvoss 的猜想 1，即保证了对所有前缀的界限，而不仅仅是终止前缀。

• 最优性： 文中指出所考虑的 $d$ 范围本质上是优的。通过引用 Kulkarni, Reis, 和 Rothvoss 的研究，他们观察到当 $d = o(\log T)$ 时，没有任何在线算法能保证 $O(\sqrt{d})$ 的差异，因为一个盲目对手（oblivious adversary）可以迫使差异达到 $\Omega(\sqrt{\log T})$。

意义
本文声称提供了第一个高效的在线算法，能够将前缀差异最小化至最优的 $O(\sqrt{d})$ 边界，直至接近对数级的稀疏度。这填补了理论离线猜想与算法在线性能之间的空白。其意义在于：

1. 算法效率： 不同于以往需要指数级时间的 Komlós 问题最优界限，该算法是高效的（在耦合构造的语境下为线性时间）。
2. 扩展猜想： 它将 Beck–Fiala 猜想的有效性推向了此前证明的远低于其之前的稀疏度区间，接近了在线算法所能达到的理论极限。
3. 解决开放问题： 它以强形式正面回答了关于前缀差异的在线 Spencer 猜想。

关于证明生成说明
作者明确指出，证明过程是在与 ChatGPT 5.6 Pro 的对话中生成的。作者提供了高层级的指导和提示，通过将三元耦合应用于有界随机行走来解决在线 Spencer 问题。AI 生成了针对 $O(\sqrt{n})$ 情况的完整证明以及特定的“凸峰密度”构造。随后，作者手动验证、重写并将这些结果整理成了最终的手稿。