# Optimal Online Discrepancy Minimization

arXiv: https://arxiv.org/abs/2308.01406 · HTML: https://mlsanity.com/paper/2308.01406/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2023.

## Built on by (most cited first, 2 of 2)

- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)

## Abstract (arXiv)

We prove that there exists an online algorithm that for any sequence of vectors v1,ldots,vT ∈ ℝn with |vi|2 ≤ 1, arriving one at a time, decides random signs x1,ldots,xT ∈  -1,1 so that for every t ≤ T, the prefix sum sumi=1t xivi 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 maxt ∈ T |sumi=1t xi vi|_∞. 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 Omega(√log T) strategy for an oblivious adversary.