Optimal Online Discrepancy Minimization in Linear Time

We provide an online algorithm with the following guarantee: for any fixed sequence of vectors $v_1,\dots ,v_T\in {\mathbf{R}}^d$ with $\mathrm{\parallel }{v}_i{\mathrm{\parallel }}_2\le 1$, the algorithm assigns each arriving vector $v_t$ a random sign ${\epsilon }_t$ such that every prefix sum ${\sum }_{i=1}^t{\epsilon }_i{v}_i$ can be written as the sum of three coupled standard Gaussian vectors. Our algorithm runs in $O(dT)$ time and achieves the optimal prefix discrepancy bound $$\underset{1\le t\le T}{\max }{\parallel \sum _{i=1}^t{\epsilon }_i{v}_i\parallel }_{\mathrm{\infty }}=O\left(\sqrt{\log T}\right),$$ with high probability. This recovers the optimal bound of Kulkarni, Reis, and Rothvoss, whose algorithm runs in time exponential in $T$ and $d$. The algorithm and main proof were discovered in a GPT-5.5 Pro Extended conversation prompted by the author.