Online Discrepancy Minimization for Stochastic Arrivals

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

In the stochastic online vector balancing problem, vectors v1, v2, …, 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 polylog(nT) factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC' 20). In particular, for the Komlós problem where ‖vt‖2 ≤ 1 for each t, our algorithm achieves Õ(1) discrepancy with high probability, improving upon the previous Õ(n3/2) bound. For Tusnády's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an O(logd+4T) 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 Õ(1) discrepancy with respect to the norm given by K for input distributions with sub-exponential tails. Our results are based on a new potential function approach. Previous techniques consider a potential that penalizes large discrepancy, and greedily chooses the next color to minimize the increase in potential. 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. We believe that our techniques to control the evolution of states could find other applications in stochastic processes and online algorithms. 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 multicolor discrepancy.
BibTeX
@inproceedings{bansal2021online,
  author = {Nikhil Bansal and Haotian Jiang and Raghu Meka and Sahil Singla and Makrand Sinha},
  title = {{Online Discrepancy Minimization for Stochastic Arrivals}},
  booktitle = {SODA},
  year = {2021},
  doi = {10.1137/1.9781611976465.169},
}

Loading related content...

Figure