Online Beck--Fiala Down to Logarithmic Sparsity
Abstract
The celebrated (offline) Beck--Fiala conjecture asserts that every matrix A∈{0,1}n× T with at most d nonzero entries in each column has discrepancy O(√d). In this note, we consider the {\it online} version of the conjecture. For every fixed η>0, we give a randomized online algorithm that achieves Oη(√d) prefix discrepancy for every fixed sequence of d-sparse vectors at∈[−1,1]n, except with probability at most CηTexp[−cηd/(log2+η(ed))]. In particular, this gives an optimal O(√d) discrepancy upper bound for d≥ Cη(log T)(loglog T)2+η. This range of sparsity is optimal up to loglog T factors. The result also resolves in strong form the {\it online Spencer problem}, corresponding to the case d = n. The algorithm is based on a compactly supported Metropolis walk, constructed by combining ideas from several recent works on online vector balancing. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.
Related
- Improved Algorithms for Beck--Fiala with Bounded Sets
- Asymptotic Bayes Optimality Under Sparsity of the Gavrilov-Benjamini-Sarkar Step-Down Testing Procedure
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Uniform Asymptotics for Andrews-Beck Partition Statistics
- Sparsity of Quadratically Regularized Optimal Transport: Scalar Case
BibTeX
@misc{altschuler2026online,
title = {{Online Beck--Fiala Down to Logarithmic Sparsity}},
author = {Dylan J. Altschuler and Konstantin Tikhomirov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2607.14238},
eprint = {2607.14238},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.14238},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Online Beck--Fiala Down to Logarithmic Sparsity
AU - Dylan J. Altschuler
AU - Konstantin Tikhomirov
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2607.14238
UR - https://arxiv.org/abs/2607.14238
AB - The celebrated (offline) Beck--Fiala conjecture asserts that every matrix A∈{0,1}^n× T with at most d nonzero entries in each column has discrepancy O(√d). In this note, we consider the {\it online} version of the conjecture. For every fixed η>0, we give a randomized online algorithm that achieves O_η(√d) prefix discrepancy for every fixed sequence of d-sparse vectors a_t∈[−1,1]^n, except with probability at most C_ηTexp[−c_ηd/(log^2+η(ed))]. In particular, this gives an optimal O(√d) discrepancy upper bound for d≥ C_η(log T)(loglog T)^2+η. This range of sparsity is optimal up to loglog T factors. The result also resolves in strong form the {\it online Spencer problem}, corresponding to the case d = n. The algorithm is based on a compactly supported Metropolis walk, constructed by combining ideas from several recent works on online vector balancing. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.
ER -