# Online Discrepancy Minimization for Stochastic Arrivals

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2020.

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

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)
- [Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance](https://mlsanity.com/paper/2504.11299/) (2025)

## Abstract (arXiv)

In the stochastic online vector balancing problem, vectors v1,v2,ldots,vT chosen independently from an arbitrary distribution in ℝn arrive one-by-one and must be immediately given a ± sign. The goal is to keep the norm of the discrepancy vector, i.e., the signed prefix-sum, as small as possible for a given target norm. We consider some of the most well-known problems in discrepancy theory in the above online stochastic setting, and give algorithms that match the known offline bounds up to mathsfpolylog(nT) factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC' 20). In particular, for the Koml'os problem where |vt|2≤ 1 for each t, our algorithm achieves tildeO(1) discrepancy with high probability, improving upon the previous tildeO(n3/2) bound. For Tusn'ady's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an O(logd+4 T) bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker O(log2d+1 T) bound. We also consider the Banaszczyk setting, where given a symmetric convex body K with Gaussian measure at least 1/2, our algorithm achieves tildeO(1) discrepancy with respect to the norm given by K for input distributions with sub-exponential tails. Our key idea is to introduce a potential that also enforces constraints on how the discrepancy vector evolves, allowing us to maintain certain anti-concentration properties. For the Banaszczyk setting, we further enhance this potential by combining it with ideas from generic chaining. Finally, we also extend these results to the setting of online multi-color discrepancy.