Optimal online discrepancy minimization

We prove that there exists an online algorithm that for any sequence of vectors $v_1,…,v_T \in R^n$ with $∥v_i∥_2 ≤1,$ arriving one at a time, decides random signs $x_1,…,x_T \in {−1,1}$ so that for every $t≤T,$ the prefix sum $∑_{i=1}^t x_1v_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{logT})$ bound on the discrepancy $max_{t∈T} ∥∑_{i=1}^t x_iv_i∥_∞.$ 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 $Ω(\sqrt{logT})$ strategy for an oblivious adversary.