Optimal online discrepancy minimization - Kulkarni, Janardhan (Jana); Reis, Victor; Rothvoss, Thomas (STOC'24, 2024)
We prove that there exists an online algorithm that for any sequence of vectors with arriving one at a time, decides random signs so that for every the prefix sum is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums -subgaussian, and gives a bound on the discrepancy 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 strategy for an oblivious adversary.