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.