CS Paper Radar

Online Discrepancy for Sub-Exponential Product Distributions via Regularization

Nicola Wengiel

cs.DS cs.DMmath.COmath.PR ·submitted 2026-08-10 09:24 UTC · v2
theory

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 $ψ_1$-norms at most $σ$, we obtain terminal discrepancy $O(σ^4\sqrt n)$ with failure probability $\exp(-Ω(σ^3\sqrt n))$. Independently masking centered unit-variance marks from the same class with retention probability $k/n$ gives $O(σ^4\sqrt k)$ discrepancy with failure probability $\exp(-Ω(σ^3\sqrt k))$ when $k\gtrsim\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(\sqrt k+\sqrt{\log(2n)})$ discrepancy with failure probability $\exp(-Ω(\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 $ψ_2$-norm bound $σ$, logarithmic sparsity suffices for $O(σ\sqrt{k\log(e+σ)})$ 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 $Θ(\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.

Comment
66 pages. Substantially revised and extended; proofs simplified

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

cs.LG ·2026-09-19 ·Zihan Zhang
theory similarity 0.63
Abstract

We study differentially private covariance estimation in operator norm for mean-zero sub-Gaussian distributions with unknown covariance support and at most $k$ nonzero entries per row. We develop a multiscale random-threshold algorithm with sample complexity $\ot(k^2/α^2+k\sqrt d/(α\varepsilon))$ for $(\varepsilon,δ)$-differential privacy and error at most $ασ^2$, where $d$ is the dimension and $σ$ is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing $\ot(k^2/α^2+k^{3/2}\sqrt d/(α\varepsilon))$ \citep{kumar2026curse} upper bound by a factor of $\sqrt k$, and matches the lower bound of $\widetildeΩ(k^2/α^2 + k\sqrt{d}/(α\varepsilon))$ in its applicable parameter regime. Our key technical ingredient is a direct operator-norm bound on the centered fluctuations of an ideal reconstruction, exploiting conditional independence rather than accumulating entrywise errors across each row. A multiscale allocation of threshold tests balances reconstruction variance against query sensitivity. Together, these ingredients sharpen the trade-off between approximation error and privacy protection, removing the additional $\sqrt{k}$ factor from the privacy-dependent sample complexity.

0.31

The threshold for online balancing of i.i.d. binary vectors

cs.DS math.PRmath.CO ·2026-09-14 ·Dylan J. Altschuler, Konstantin Tikhomirov
theory similarity 0.62
Abstract · Supersedes and replaces arxiv.org/abs/2509.02432, which has the same lower bound, but only has an upper bound for the ultra-sparse regime

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^tσ_i X_i\right\|_\infty$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $Θ(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $Θ(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.

0.44

Stable and Online Algorithms for Random Matrix Discrepancy

cs.DS cs.CCcs.DMmath.CO+1 ·2026-10-01 ·Eren C. Kızıldağ, Shuangping Li
theoryhighly cited similarity 0.61
Abstract

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs $σ_1,\dots,σ_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N σ_i A_i$ is at most $κ\sqrt{N}$. Focusing on the proportional regime $N/d^2\to τ\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $κ\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time \emph{recenter-and-round} algorithm that is noise-stable and succeeds whenever $τ=Ω(\frac{1}{κ^2\log(1/κ)})$, along with a matching lower bound for all stable algorithms. In the online setting where each sign must be chosen irrevocably upon observing the corresponding matrix, we determine the exact limiting performance of the \emph{Frobenius-greedy} algorithm, establishing that it succeeds when $τ>τ_{\rm FG}(κ)\sim \fracπ{4κ^2}$, as well as a matching lower bound for all online algorithms by conditioning on a revealed prefix. At the core of our algorithms lies rotational symmetry, which enables us to transfer Frobenius norm control into operator norm guarantees. Together, our results identify the algorithmic phase transition points for random matrix discrepancy: $Θ(\frac{1}{κ^2\log(1/κ)})$ for stable offline algorithms and $Θ(\frac{1}{κ^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $Θ(\log(1/κ))$, as shown by Maillard~\cite{maillard2025}.

0.30

Exact Universality of Online Discrepancy

cs.DS math.PR ·2026-09-08 ·Sunghyeon Jo, Taekyun Lee
theory similarity 0.59
Abstract · 40 pages

We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected $\ell^\infty$ 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\toα\in(0,\infty)$, the optimal value divided by $\sqrt 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 $\ell^\infty$ norm at most $κ\sqrt 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.

0.44

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.58
Abstract · 36 pages

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

0.13

Tusnády's problem and online two-sample thinning

cs.DS math.COmath.PR ·2026-11-05 ·Yuhao Lei
theory similarity 0.58
Abstract · 40 pages, 5 figures

We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$. The largest combinatorial discrepancy of $N$ points in $\mathbb{R}^d$ with respect to axis-parallel boxes is $Θ_d((\log N)^{d-1/2})$, extending Wei's planar result and matching Nikolov's upper bound. More strongly, with high probability, this lower bound holds simultaneously for every subset obtained by deleting at most a sufficiently small fixed fraction of a uniform $N$-point sample. We apply this geometric estimate to online thinning of two independent samples of size $n$ from an unknown common distribution, where observations must be kept or discarded upon arrival. For every fixed dimension $k\ge 1$ and expected deletion budget $ρn$, with $0<ρ<2$, we prove that the minimax expected prefix discrepancy over lower orthants is $Θ_{k,ρ}((\log n)^{k+1/2})$. In dimension one, the optimal terminal discrepancy is instead $Θ_ρ((\log\log n)^{3/2})$, giving a sharp separation between the prefix and terminal objectives. For $k\ge 2$, we obtain terminal bounds differing by a factor of $\log n$. The lower bounds are based on Gaussian small-ball estimates for box-incidence matrices, while the upper bounds use stationary Metropolis thinning and, in one dimension, a terminal cancellation procedure.

0.37

Near-Optimal Bounds for Sketching the Schatten Norms

cs.DS cs.CCmath.ST ·2026-08-23 ·Lin F. Yang
theory similarity 0.58
Abstract · 94 pages, added the turnstile streaming lower bound, upper/lower bound for all non-even p>0

Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log n)^{A_\varepsilon}} \le k_{1,\varepsilon}(n) \le C_\varepsilon \frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)}. \] Previously, the best unrestricted bounds for general linear sketches of the Schatten--1 norm were $Ω(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff'19), leaving a polynomial gap. Our bounds close that gap up to polylogarithmic factors and give a nontrivial logarithmic saving below the $n^2$-measurement storage bound. The result extends much further. Write $k_{p,\varepsilon}(n)$ for the analogous sketch dimension for the Schatten--$p$ norm. For every fixed finite $p>0$ that is not a positive even integer, there are positive constants $A_{p,\varepsilon},C_{p,\varepsilon},c_p$ such that \[ \frac{n^2}{(\log n)^{A_{p,\varepsilon}}} \le k_{p,\varepsilon}(n) \le C_{p,\varepsilon}\frac{n^2}{(\log n)^{c_p}}, \] so $k_{p,\varepsilon}(n)=n^{2-o(1)}$ throughout the non-even regime. Together with the known tight bounds $Θ_{p,\varepsilon}(n^{2-4/p})$ for positive even $p$ and $Θ_\varepsilon(n^2)$ for $p=\infty$ (Li, Woodruff'16), our results close the remaining polynomial gap across the Schatten family and complete, up to polylogarithmic factors, the polynomial-order classification of general linear sketches for all Schatten-$p$ norms.

0.16

The Exact Online Threshold for the Asymmetric Binary Perceptron

cs.DS ·2026-09-02 ·Sunghyeon Jo, Taekyun Lee
highly cited similarity 0.58
Abstract · 56 pages

Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $κ\in\mathbb{R}$, the asymmetric binary perceptron asks for $σ\in\{\pm1\}^N$ such that $Gσ/\sqrt{N}\geκ\mathbf{1}_M$. We study the online version of this problem, in which the columns of $G$ arrive sequentially and each sign must be chosen irrevocably before future columns are revealed. We determine the exact threshold $α_{\mathrm{on}}(κ)$ for every fixed $κ$: for $M/N\toα$ with $α<α_{\mathrm{on}}(κ)$, there is a deterministic online algorithm, using $O(MN)$ arithmetic operations and polynomial bit complexity, that succeeds with high probability, while for $α>α_{\mathrm{on}}(κ)$, no online algorithm succeeds with high probability. The threshold is characterized by a one-dimensional stochastic control problem for Brownian motion. The main difficulty is to upgrade a single-coordinate Brownian limit to simultaneous feasibility of all $M=Θ(N)$ constraints, which we do with half-line monotonicity and a short final correction block. At zero margin, we give a computer-assisted proof that $0.32747<α_{\mathrm{on}}(0)<0.36664$. In particular, every density below $0.32747$ is achievable online by such an algorithm, more than tripling the best density previously proved attainable by any polynomial-time algorithm, online or offline (the previous bound was $α\le0.1$, due to Li, Schramm, and Zhou). As $κ\to+\infty$, the online threshold agrees to first order with the offline storage capacity. As $κ\to-\infty$, it has the same asymptotic scale as the best known offline polynomial-time guarantee, while the storage capacity is larger by a factor of order $κ^2$.

0.57