Online Beck--Fiala Down to Logarithmic Sparsity

Technical Summary: Online Beck–Fiala Down to Logarithmic Sparsity

Problem Statement
The paper addresses the Beck–Fiala conjecture, a central problem in combinatorial discrepancy theory. The conjecture posits that for any binary matrix $A \in \{0, 1\}^{n \times T}$ where each column has at most $d$ non-zero entries, there exists a signing $\varepsilon \in \{-1, 1\}^T$ such that the discrepancy $\|A\varepsilon\|_\infty$ is bounded by $O(\sqrt{d})$. Crucially, this bound should be independent of the dimensions $n$ and $T$.

While the offline version of the problem has seen significant progress (notably Bansal and Jiang establishing the bound for $d \ge \log(T)^2$), the online variant remains more challenging. In the online setting, vectors $a_1, \dots, a_T$ are revealed sequentially, and the algorithm must irrevocably choose signs $\varepsilon_t$ to minimize the prefix discrepancy $\max_{t \le T} \|\sum_{s=1}^t \varepsilon_s a_s\|_\infty$. Prior to this work, the best known algorithmic bound for the online Beck–Fiala problem was $O(\sqrt{d \log T})$, derived from general Komlós results.

Methodology
The authors develop an efficient randomized online algorithm based on a compactly supported Metropolis fixed-point walk. The core methodology involves three main components:

1. Triplet Coupling: The algorithm maintains three coupled random walks $(X_{t,1}, X_{t,2}, X_{t,3})$ evolving in a bounded domain $(-L, L)^n$. At each step, the algorithm uses a three-way coupling lemma (adapted from Aden-Ali) to sample increments $\delta_{t,j} \in \{-1, 0, 1\}$ for each walk such that their sum $\varepsilon_t = \sum \delta_{t,j}$ is a genuine sign in $\{-1, 1\}$.
2. Stationary Measure and Balance: The walks are designed to be stationary with respect to a specific product measure $\mu = \rho^{\otimes n}$. The algorithm ensures that the current state $X_{t-1}$ is "balanced" with respect to the incoming vector $v_t$. A state is $v$-balanced if the probability of moving in the direction of $v$ or $-v$ is sufficiently high (specifically, $p^+_v + p^-_v \ge 1/3$). If the state is balanced, the coupling ensures the sum of increments cancels out the drift, keeping the prefix sum bounded.
3. Scale-Sensitive Curvature and Bump Densities: To handle sparse vectors (where $d$ is small), the authors construct a specific invariant density $\rho$ (a "bump law") supported on $(-1, 1)$. This density is defined via a potential function $\Phi_\beta(y) = e^{(1-y^2)^{-\beta}}$. The proof relies on analyzing the curvature of this potential. They establish that for sparse vectors, the "curvature tail" (the probability that the potential changes too drastically) is exponentially small. This allows them to bound the probability that the walk becomes unbalanced.

Key Contributions and Results

• Theorem 1.1 (Online Beck–Fiala): The authors present a randomized online algorithm that achieves a prefix discrepancy of $O(\sqrt{d})$ for sparsity parameters $d$ satisfying $d \ge C (\log T)(\log \log T)^{2+\eta}$.

  • The failure probability is bounded by $C_\eta T \exp\left(-\frac{c_\eta d}{\log^{2+\eta}(ed)}\right)$.
  • This effectively extends the validity of the Beck–Fiala conjecture to the nearly logarithmic sparsity regime, a significant improvement over the previous $d \ge \log(T)^2$ threshold for offline results and the $O(\sqrt{d \log T})$ bound for online results.

• Corollary 1.2 (Offline Beck–Fiala): As a direct consequence, the offline Beck–Fiala conjecture is established for matrices with column sparsity $d$ in the same logarithmic regime.

• Corollary 1.3 (Online Prefix Spencer): The result resolves the open question of online vector balancing in the Spencer setting (where vectors are in $[-1, 1]^n$). The authors prove that for $T \le \exp\left(\frac{c_\eta n}{\log^{2+\eta}(en)}\right)$, there exists an online algorithm achieving prefix discrepancy $O(\sqrt{n})$. This confirms Conjecture 1 of Kulkarni, Reis, and Rothvoss in a strong form, guaranteeing bounds for all prefixes, not just the terminal one.

• Optimality: The paper notes that the range of $d$ considered is essentially optimal. Citing Kulkarni, Reis, and Rothvoss, they observe that for $d = o(\log T)$, no online algorithm can guarantee $O(\sqrt{d})$ discrepancy, as an oblivious adversary can force a discrepancy of $\Omega(\sqrt{\log T})$.

Significance
The paper claims to provide the first efficient online algorithm that minimizes prefix discrepancy to the optimal $O(\sqrt{d})$ bound down to nearly logarithmic sparsity. This bridges a gap between the theoretical offline conjecture and algorithmic online performance. The significance lies in:

1. Algorithmic Efficiency: Unlike previous optimal bounds for the Komlós problem which required exponential time, this algorithm is efficient (linear time in the context of the coupling construction).
2. Extension of Conjectures: It pushes the validity of the Beck–Fiala conjecture into a regime where the sparsity is much lower than previously proven, approaching the theoretical limit of what is possible for online algorithms.
3. Resolution of Open Problems: It positively answers the strong form of the online Spencer conjecture regarding prefix discrepancy.

Note on Proof Generation
The authors explicitly state that the proof was generated in conversation with ChatGPT 5.6 Pro. The authors provided high-level guidance and prompting to solve the online Spencer problem by applying triplet coupling to a bounded random walk. The AI generated the complete proof for the $O(\sqrt{n})$ case and the specific "bump density" construction. The authors then manually verified, rewrote, and organized these results into the final manuscript.