Exact Universality of Online Discrepancy
Abstract
We study online vector balancing with N random vectors in ℝM revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected ℓ∞ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth moment, we prove that, as M/N→α∈(0,∞), the optimal value divided by √N converges to a limit Rα independent of the entry distribution. This limit is the stochastic control value identified for Gaussian inputs by Fiedler, Jackson, Lacker, and Niles-Weed. In particular, it determines the exact asymptotic optimum for Rademacher inputs. For every κ>Rα, we construct a randomized online algorithm whose final signed sum has ℓ∞ norm at most κ√N with high probability; for κ<Rα, every online algorithm has vanishing success probability. Consequently, the online threshold of the symmetric binary perceptron is universal at every positive margin. The main step is a coupling that transfers Brownian controls to non-Gaussian inputs, while truncation controls rare large entries.
Related
- Stable and Online Algorithms for Random Matrix Discrepancy
- Online Discrepancy for Sub-Exponential Product Distributions via Regularization
- Online Discrepancy of Sparse Random Vectors over Long Horizons
- Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces
- K-spherical horospherical averages on the Nagao quotient: tree combinatorics and exact discrepancy
BibTeX
@misc{jo2026exact,
title = {{Exact Universality of Online Discrepancy}},
author = {Sunghyeon Jo and Taekyun Lee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00103},
eprint = {2610.00103},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00103},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Universality of Online Discrepancy
AU - Sunghyeon Jo
AU - Taekyun Lee
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00103
UR - https://arxiv.org/abs/2610.00103
AB - We study online vector balancing with N random vectors in ℝ^M revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected ℓ^∞ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth moment, we prove that, as M/N→α∈(0,∞), the optimal value divided by √N converges to a limit R_α independent of the entry distribution. This limit is the stochastic control value identified for Gaussian inputs by Fiedler, Jackson, Lacker, and Niles-Weed. In particular, it determines the exact asymptotic optimum for Rademacher inputs. For every κ>R_α, we construct a randomized online algorithm whose final signed sum has ℓ^∞ norm at most κ√N with high probability; for κ<R_α, every online algorithm has vanishing success probability. Consequently, the online threshold of the symmetric binary perceptron is universal at every positive margin. The main step is a coupling that transfers Brownian controls to non-Gaussian inputs, while truncation controls rare large entries.
ER -