@inproceedings{kulkarni2024optimal,
author = {Kulkarni, Janardhan (Jana) and Reis, Victor and Rothvoss, Thomas},
title = {Optimal online discrepancy minimization},
booktitle = {STOC'24},
year = {2024},
month = {March},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/optimal-online-discrepancy-minimization/},
}