Optimal Online Discrepancy Minimization

Abstract

We prove that there exists an online algorithm that for any sequence of vectors $v_1,\dots ,v_T\in {\mathbb{R}}^n$ with $\Vert v_i{\Vert }_2\le 1$, arriving one at a time, decides random signs $x_1,\dots ,x_T\in \{-1,1\}$ so that for every $t\le T$, the prefix sum ${\sum }_{i=1}^t{x}_i{v}_i$ is $10$-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums $O(\sqrt{\log (nT)})$-subgaussian, and gives a $O(\sqrt{\log T})$ bound on the discrepancy ${\max }_{t\in T}\Vert {\sum }_{i=1}^t{x}_i{v}_i{\Vert }_{\infty }$. Our proof combines a generalization of Banaszczyk's prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching $\Omega (\sqrt{\log T})$ strategy for an oblivious adversary.

22 pages