Online Discrepancy Minimization for Stochastic Arrivals

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

Abstract In the stochastic online vector balancing problem, vectors $v_1, v_2, \dots, v_T$ are sampled independently from an arbitrary distribution in $\mathbb{R}^n$. As each vector arrives, an algorithm must immediately assign it a sign $\chi_t \in \{+1, -1\}$ to minimize the norm of the discrepancy vector—the signed prefix-sum $d_t = \sum_{i=1}^t \chi_i v_i$. This paper presents algorithms that match known offline discrepancy bounds up to $\mathsf{polylog}(nT)$ factors, significantly generalizing and improving upon previous work. For the Komlós problem, we achieve $\tilde{O}(1)$ discrepancy, improving the prior $\tilde{O}(n^{3/2})$ bound. For Tusnády's problem, we obtain an $O(\log^{d+4} T)$ bound for arbitrary distributions, moving beyond the limitations of product distributions. Our approach centers on a novel potential function that maintains anti-concentration properties, combined with generic chaining for complex convex bodies.

Introduction

Discrepancy theory asks how to partition a collection of objects into two balanced sets. In the context of vectors, the goal is to assign signs to a sequence of vectors such that their signed sum remains as close to the origin as possible. While the offline version of this problem—where all vectors are known in advance—is well-understood through landmark results like Banaszczyk’s Theorem and the Komlós conjecture, the online setting presents a formidable challenge.

In a fully adversarial online setting, where an opponent chooses vectors to maximize imbalance, the discrepancy can grow as $\Omega(\sqrt{T})$. To achieve more practical and tighter bounds, researchers focus on the stochastic setting, where vectors are drawn i.i.d. from a distribution $p$. Previous attempts to solve the stochastic online problem often resulted in bounds that scaled poorly with the dimension $n$ or required restrictive assumptions, such as the distribution being a product distribution. This research bridges the gap between online stochastic arrivals and optimal offline bounds.

The Challenge of State Control

Standard online algorithms typically employ potential functions that penalize the magnitude of the current discrepancy vector $d_t$. At each step, the algorithm chooses a sign $\chi_t$ to minimize the immediate increase in this potential. However, this "greedy" approach is insufficient for long-term stability.

The critical insight of this work is that an algorithm must not only minimize current error but also manage the distribution of its future states. If the discrepancy vector $d_t$ becomes nearly orthogonal to the support of the input distribution $p$, the algorithm loses its ability to "cancel out" future vectors. To prevent this, the algorithm must ensure that $d_t$ maintains anti-concentration—staying in a state where it is likely to have a significant inner product with future arrivals.

Methodology: Anti-Concentration and Potential Functions

To enforce this structural constraint, the authors introduce a potential function based on exponential moments:

$$\Phi_t \sim \mathbb{E}_v[\exp(\lambda |\langle d_t, v \rangle|)]$$

By tracking how the discrepancy vector interacts with the underlying distribution, the potential function penalizes states where the discrepancy is "hidden" from future vectors. This ensures that the algorithm always retains the leverage needed to steer the discrepancy back toward zero.

Handling Complex Constraints

For the Banaszczyk setting, where the goal is to keep the discrepancy within a symmetric convex body $K$, the number of constraints can be infinite or exponential. The authors address this by integrating their potential function with generic chaining. This technique, borrowed from the study of stochastic processes, allows the algorithm to manage constraints across multiple spatial scales simultaneously, providing a robust framework for high-dimensional vector balancing.

Key Results

The paper provides near-optimal bounds for several classic problems in discrepancy theory under stochastic arrivals:

  1. The Komlós Problem: For vectors with $\|v_t\|_2 \leq 1$, the algorithm achieves $\tilde{O}(1)$ discrepancy with high probability. This is a massive improvement over the previous state-of-the-art online bound of $\tilde{O}(n^{3/2})$ and matches the offline Komlós conjecture up to logarithmic factors.
  2. Tusnády’s Problem: In the problem of minimizing discrepancy for axis-aligned boxes in $d$ dimensions, the algorithm achieves a bound of $O(\log^{d+4} T)$. Crucially, this result holds for arbitrary distributions, whereas previous online results were restricted to product distributions.
  3. Banaszczyk Setting: For any symmetric convex body $K$ with Gaussian measure at least $1/2$, the algorithm maintains the discrepancy within a $\tilde{O}(1)$ factor of $K$ for input distributions with sub-exponential tails.
  4. Multi-color Discrepancy: The framework extends to the multi-color setting, where each vector must be assigned one of $R$ colors, maintaining balance across all color classes.

Conclusion and Future Work

This work demonstrates that the "online" nature of stochastic discrepancy minimization only incurs a polylogarithmic penalty compared to the offline setting. By focusing on the evolution of the discrepancy vector's distribution rather than just its magnitude, the authors provide a powerful template for online stochastic optimization.

Future research may focus on tightening the exponents of the polylogarithmic factors and exploring whether these anti-concentration techniques can be adapted for distributions with heavier tails or for settings with limited dependencies between arrivals.

Summary updated

Abstract

In the stochastic online vector balancing problem, vectors $v_1,v_2,\ldots,v_T$ chosen independently from an arbitrary distribution in $\mathbb{R}^n$ arrive one-by-one and must be immediately given a $\pm$ 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 $\mathsf{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\'{o}s problem where $\|v_t\|_2\leq 1$ for each $t$, our algorithm achieves $\tilde{O}(1)$ discrepancy with high probability, improving upon the previous $\tilde{O}(n^{3/2})$ bound. For Tusn\'{a}dy's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an $O(\log^{d+4} T)$ bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker $O(\log^{2d+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 $\tilde{O}(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.
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},
}
Figure