Optimal Online Discrepancy Minimization

We prove that there exists an online algorithm that for any sequence of vectors v 1 , . . . , v T ∈ R n with v i 2 ≤ 1, arriving one at a time, decides random signs x 1 , . . . , x T ∈ -1, 1 so that for every t ≤ T , the prefix sum t i =1 x i v i 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( log T ) bound on the discrepancy max t ∈T t i =1 x i v 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 Ω( log T ) strategy for an oblivious adversary.