Online Discrepancy for Sub-Exponential Product Distributions via Regularization

Abstract

We study online discrepancy minimization for independent random vectors in ${\mathbb{R}}^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 ${\psi }_1$-norms at most $\sigma$, we obtain terminal discrepancy $O({\sigma }^4\sqrt{n})$ with failure probability $\exp (-\Omega ({\sigma }^3\sqrt{n}))$. Independently masking centered unit-variance marks from the same class with retention probability $k/n$ gives $O({\sigma }^4\sqrt{k})$ discrepancy with failure probability $\exp (-\Omega ({\sigma }^3\sqrt{k}))$ when $k\gtrsim {\log }^2(2n)$. The fourth-power dependence on $\sigma$ is necessary for these sub-exponential classes at the stated confidence levels. For standard Gaussian marks, we obtain $O(\sqrt{k}+\sqrt{\log (2n)})$ discrepancy with failure probability $\exp (-\Omega (\sqrt{k}+\sqrt{\log (2n)}))$. Both terms are necessary up to absolute constants for $T\ge n$. In particular, $k\gtrsim \log n$ is the optimal sparsity threshold for $O(\sqrt{k})$ discrepancy. For centered unit-variance sub-Gaussian marks with any fixed ${\psi }_2$-norm bound $\sigma$, logarithmic sparsity suffices for $O(\sigma \sqrt{k\log (e+\sigma )})$ discrepancy with probability tending to one as $n\to \infty$. For a dimension-dependent family of unit-variance laws with rare activations, matching bounds determine the fixed-confidence online discrepancy order $\Theta (\sqrt{n}\log \log 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(\sqrt{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.

arXiv comment66 pages. Substantially revised and extended; proofs simplified