Optimal Online Discrepancy Minimization

We prove that there exists an online algorithm that for any sequence of vectors v1,…,vT ∈ ℝn with ||vi||2 ≤ 1, arriving one at a time, decides random signs x1,…,xT ∈ −1,1 so that for every t ≤ T, the prefix sum ∑i=1t xivi is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums O(√log(nT))-subgaussian, and gives a O(√logT) bound on the discrepancy maxt ∈ T ||∑i=1t xi vi||∞. 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 Ω(√logT) strategy for an oblivious adversary.