Online Discrepancy Minimization for Sub-Gaussian Inputs via Regularization and Restriction

Abstract

We study online discrepancy minimization: vectors $v_1,\dots ,v_T\in {\mathbb{R}}^n$ arrive sequentially, and each must immediately be assigned a sign $x_t\in \{\pm 1\}$, with the aim of minimizing $\Vert {\sum }_{t=1}^T{x}_t{v}_t{\Vert }_{\infty }$. We give a polynomial-time potential-based algorithm combining a regularization of the ${\ell }_{\infty }$-norm with restriction to an adaptively chosen coordinate set. For i.i.d. inputs with independent, symmetric, centered, unit-variance sub-Gaussian coordinates of sub-Gaussian norm at most $\sigma$, the algorithm achieves terminal discrepancy $O({\sigma }^8\sqrt{n})$ with probability at least $1-\exp (-\Omega ({\sigma }^3\sqrt{n}))$. If the coordinates are independently masked by Bernoulli variables with mean $k/n$, where $k\gtrsim (\log n{)}^2$, the bound improves to $O({\sigma }^8\sqrt{k})$, with failure probability $\exp (-\Omega ({\sigma }^3\sqrt{k}))$. Both guarantees hold for every prescribed finite horizon $T$, with no dependence on $T$. The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022). When $T$ is polynomially larger than $n$, this is conditionally close to optimal: under worst-case hardness assumptions for standard approximate lattice problems, Vafa and Vaikuntanathan (2025) showed that no polynomial-time algorithm, even offline, can improve the $\sqrt{n}$ scale by a fixed polynomial factor in $T/n$.