This paper, presented at STOC 2020, tackles a fundamental challenge in online algorithms and discrepancy theory: how to balance a sequence of vectors arriving one-by-one to keep their total sum as small as possible.
TL;DR
The authors provide near-optimal algorithms for online discrepancy minimization when input vectors are sampled from a stochastic distribution. By introducing a novel potential function that enforces "anti-concentration" properties, they match classic offline bounds for the Komlós, Tusnády, and Banaszczyk problems up to polylogarithmic factors, significantly outperforming previous online approaches.
What Problem Does This Paper Address?
Imagine you are given a sequence of vectors $v_1, v_2, \dots, v_T$ in $\mathbb{R}^n$. For each vector, you must immediately and irrevocably choose a sign $\chi_t \in \{+1, -1\}$. Your goal is to keep the "discrepancy vector"—the signed prefix sum $d_t = \sum_{i=1}^t \chi_i v_i$—as small as possible under some norm (like the $\ell_\infty$ norm).
In the offline setting (where you see all vectors in advance), famous results like the Komlós conjecture and Banaszczyk’s Theorem provide very tight bounds. However, the online setting is much harder. If an adversary chooses the vectors, they can force the discrepancy to grow as $\Omega(\sqrt{T})$.
To bypass this "curse of the adversary," researchers look at the stochastic setting, where vectors are chosen independently from a distribution $p$. Previous work in this area often suffered from a heavy dependence on the dimension $n$ or only worked for very specific distributions (like product distributions). This paper aims to bridge the gap between offline and online stochastic bounds for arbitrary distributions.
Methods
The core of the paper is a Potential Function Approach.
- Standard Potential Functions: Usually, online algorithms use a potential function that penalizes the state if the discrepancy vector $d_t$ gets too large. You then choose the sign $\chi_t$ that minimizes the increase in this potential.
- The "Anti-Concentration" Innovation: The authors realized that simply minimizing the current error isn't enough. You also need to ensure that the discrepancy vector $d_t$ stays in a "good" state for future arrivals. Specifically, you want $d_t$ to have a large inner product with future random vectors $v_{t+1}$, allowing you to pick a sign that cancels out existing error.
- Exponential Moments: They introduce a potential that tracks the exponential moments of the inner product: $\Phi_t \sim \mathbb{E}_v[\exp(\lambda |\langle d_t, v \rangle|)]$. This enforces a structural constraint on how the discrepancy evolves, ensuring it doesn't become "orthogonal" to the input distribution.
- Generic Chaining: For the Banaszczyk setting (balancing vectors relative to a convex body $K$), the number of constraints can be exponential. The authors combine their potential function with generic chaining—a sophisticated tool from probability theory—to manage these constraints across multiple scales.
Datasets
As a theoretical computer science paper, no empirical datasets were used. The results are proven mathematically for any distribution $p$ satisfying certain tail conditions (like sub-exponential tails).
Key Insights and Ideas
- State Control: The "aha moment" is that an online algorithm should manage the distribution of its possible future states, not just its current error. By forcing the discrepancy vector to maintain anti-concentration, the algorithm "guarantees" itself opportunities to reduce error in the future.
- Matching Offline Bounds: The paper shows that for stochastic arrivals, the "online" nature of the problem only costs a few extra logarithmic factors compared to the best possible offline solutions.
- Universality: Their approach to Tusnády’s problem (discrepancy of axis-aligned boxes) works for arbitrary distributions of points, whereas all previous techniques required the points to be independent in each dimension (product distributions).
Key Results
The paper achieves several "firsts" and "bests" for online stochastic discrepancy:
- Komlós Problem: Achieves $O(\text{polylog}(nT))$ discrepancy. This is a massive improvement over the previous best bound of $O(n^{3/2})$.
- Tusnády’s Problem: Obtains an $O(\log^{d+4} T)$ bound for arbitrary distributions in $d$ dimensions, essentially matching the best offline bounds.
- Banaszczyk Setting: For a symmetric convex body $K$ with Gaussian measure $\ge 1/2$, the algorithm maintains $d_t \in O(\text{polylog}(nT)) \cdot K$.
- Multi-color Discrepancy: They show their potential function approach can be extended to the setting where you must assign one of $R$ colors to each vector instead of just $\pm 1$.
Limitations and Future Work
- Stochastic Assumption: The results rely heavily on the vectors being i.i.d. (or at least independent). They do not apply to the fully adversarial online setting.
- Polylog Factors: While the bounds are near-optimal, the exponents on the logarithmic factors (e.g., $\log^4$ or $\log^5$) are somewhat high. Future work could focus on "tightening" these constants.
- Tail Conditions: The Banaszczyk results require the input distribution to have sub-exponential tails. Exploring whether these techniques work for heavier-tailed distributions remains an open question.
Summary updated