# Online Vector Balancing and Geometric Discrepancy

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2019.

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

- [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)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [On The Universality of Diagrams for Causal Inference and The Causal Reproducing Property](https://mlsanity.com/paper/2207.02917/) (2022)
- [Online Fair Allocation of Perishable Resources](https://mlsanity.com/paper/2406.02402/) (2024)
- [Universal Decision Learners](https://mlsanity.com/paper/2605.30694/) (2026)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)
- [Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors](https://mlsanity.com/paper/2607.22935/) (2026)

## Abstract (arXiv)

We consider an online vector balancing question where T vectors, chosen from an arbitrary distribution over [-1,1]n, arrive one-by-one and must be immediately given a ± sign. The goal is to keep the discrepancy small as possible. A concrete example is the online interval discrepancy problem where T points are sampled uniformly in [0,1], and the goal is to immediately color them ± such that every sub-interval remains nearly balanced. As random coloring incurs Omega(T1/2) discrepancy, while the offline bounds are Theta(√n log (T/n)) for vector balancing and 1 for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is Omega(T1/2) for any online algorithm. Bansal and Spencer recently show an O(√nlog T) bound when each coordinate is independent. When there are dependencies among the coordinates, the problem becomes much more challenging, as evidenced by a recent work of Jiang, Kulkarni, and Singla that gives a non-trivial O(T1/loglog T) bound for online interval discrepancy. Although this beats random coloring, it is still far from the offline bound. In this work, we introduce a new framework for online vector balancing when the input distribution has dependencies across coordinates. This lets us obtain a poly(n, log T) bound for online vector balancing under arbitrary input distributions, and a poly(log T) bound for online interval discrepancy. Our framework is powerful enough to capture other well-studied geometric discrepancy problems; e.g., a poly(logd (T)) bound for the online d-dimensional Tusn'ady's problem. A key new technical ingredient is an anti-concentration inequality for sums of pairwise uncorrelated random variables.