Online Discrepancy for Sub-Exponential Product Distributions via Regularization
Abstract
We study online discrepancy minimization for independent random vectors in ℝn with independent coordinates. Our deterministic algorithms require no knowledge of the horizon, and their guarantees hold at every prescribed deterministic terminal time T. For unit-variance sub-exponential coordinates with ψ1-norms at most σ, we obtain terminal discrepancy O(σ4√n) with failure probability exp(−Ω(σ3√n)). Independently masking centered unit-variance marks from the same class with retention probability k/n gives O(σ4√k) discrepancy with failure probability exp(−Ω(σ3√k)) when k≳log2(2n). The fourth-power dependence on σ is necessary for these sub-exponential classes at the stated confidence levels. For standard Gaussian marks, we obtain O(√k+√(log(2n))) discrepancy with failure probability exp(−Ω(√k+√(log(2n)))). Both terms are necessary up to absolute constants for T≥ n. In particular, k≳log n is the optimal sparsity threshold for O(√k) discrepancy. For centered unit-variance sub-Gaussian marks with any fixed ψ2-norm bound σ, logarithmic sparsity suffices for O(σ√(klog(e+σ))) discrepancy with probability tending to one as n→∞. For a dimension-dependent family of unit-variance laws with rare activations, matching bounds determine the fixed-confidence online discrepancy order Θ(√nloglog n) at sufficiently long prescribed horizons. Our dense result generalizes the Rademacher-input theorem of Bansal and Spencer (2020) and establishes the horizon-independent O(√n) Gaussian terminal discrepancy scale anticipated by Gamarnik et al. (2022). The proofs combine regularization, global Fenchel estimates, coupled Lyapunov functions, and terminal moment recursions.
Related
- Exact Universality of Online Discrepancy
- Stable and Online Algorithms for Random Matrix Discrepancy
- Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter
- Adaptive Regularization via Extreme Value Distributions for Gaussian Graphical Models
- Online Discrepancy of Sparse Random Vectors over Long Horizons
BibTeX
@misc{wengiel2026online,
title = {{Online Discrepancy for Sub-Exponential Product Distributions via Regularization}},
author = {Nicola Wengiel},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.10040},
eprint = {2608.10040},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.10040},
}
RIS
TY - UNPB
TI - Online Discrepancy for Sub-Exponential Product Distributions via Regularization
AU - Nicola Wengiel
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2608.10040
UR - https://arxiv.org/abs/2608.10040
AB - We study online discrepancy minimization for independent random vectors in ℝ^n with independent coordinates. Our deterministic algorithms require no knowledge of the horizon, and their guarantees hold at every prescribed deterministic terminal time T. For unit-variance sub-exponential coordinates with ψ_1-norms at most σ, we obtain terminal discrepancy O(σ^4√n) with failure probability exp(−Ω(σ^3√n)). Independently masking centered unit-variance marks from the same class with retention probability k/n gives O(σ^4√k) discrepancy with failure probability exp(−Ω(σ^3√k)) when k≳log^2(2n). The fourth-power dependence on σ is necessary for these sub-exponential classes at the stated confidence levels. For standard Gaussian marks, we obtain O(√k+√(log(2n))) discrepancy with failure probability exp(−Ω(√k+√(log(2n)))). Both terms are necessary up to absolute constants for T≥ n. In particular, k≳log n is the optimal sparsity threshold for O(√k) discrepancy. For centered unit-variance sub-Gaussian marks with any fixed ψ_2-norm bound σ, logarithmic sparsity suffices for O(σ√(klog(e+σ))) discrepancy with probability tending to one as n→∞. For a dimension-dependent family of unit-variance laws with rare activations, matching bounds determine the fixed-confidence online discrepancy order Θ(√nloglog n) at sufficiently long prescribed horizons. Our dense result generalizes the Rademacher-input theorem of Bansal and Spencer (2020) and establishes the horizon-independent O(√n) Gaussian terminal discrepancy scale anticipated by Gamarnik et al. (2022). The proofs combine regularization, global Fenchel estimates, coupled Lyapunov functions, and terminal moment recursions.
ER -