Online Discrepancy Minimization via Persistent Self-Balancing Walks

Abstract

We study the online discrepancy minimization problem for vectors in ${\mathbb{R}}^d$ in the oblivious setting where an adversary is allowed fix the vectors $x_1,x_2,\dots ,x_n$ in arbitrary order ahead of time. We give an algorithm that maintains $O(\sqrt{\log (nd/\delta )})$ discrepancy with probability $1-\delta$, matching the lower bound given in [Bansal et al. 2020] up to an $O(\sqrt{\log \log n})$ factor in the high-probability regime. We also provide results for the weighted and multi-color versions of the problem.

The proof of Lemma 7 is incorrect. There is a serious issue that we don't know how to fix at the moment. We thank Yang, Nikhil and collaborators for bringing it to our attention