Online Discrepancy Minimization

The online discrepancy minimization problem asks, given unit vectors v_1, ..., v_t arriving one at a time, for online signs x_1 ..., x_t4 in {-1, 1} so that the signed sum x_1 v_1 + ... + x_t v_t has small coordinates in absolute value.

In the first half of the talk, we survey previous work in the adaptive and oblivious settings. In the second half, we present an online algorithm for the oblivious setting which keeps signed sums 10-subgaussian.

Based on joint work with Janardhan Kulkarni and Thomas Rothvoss.