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:
- 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.
- 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.
- 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.
- 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