Online Discrepancy Minimization via Persistent Self-Balancing Walks

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\mathrm{/}\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.