CS Paper Radar

Online Discrepancy of Sparse Random Vectors over Long Horizons

Nicola Wengiel

cs.DS cs.DMmath.COmath.PR ·submitted 2026-10-25 16:10 UTC · v1
theory

Abstract

We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of $s$ of the $n$ coordinates, with nonzero entries equal to one (binary model) or independent random signs (signed model), and an online algorithm must sign each vector upon arrival. The prefix discrepancy is the largest $\ell_\infty$-norm of the signed sums up to the horizon $T$, the terminal discrepancy that of the sum at time $T$. For binary inputs with $2\le s\le n/2$ and $T=Θ(n)$, Altschuler and Tikhomirov showed that both are of order $\sqrt{s}+\log\log n$; they asked how the prefix discrepancy depends on the horizon and whether a matching terminal bound holds at every prescribed time. Over long horizons, the two differ. For every fixed $s\ge2$ and $c>0$, every online algorithm, even a randomized one that knows the horizon, incurs with high probability prefix discrepancy $Ω(\log\log n+(\log T/\log n)^{α_s})$ for $n\le T\le e^{cn}$, where $α_s=(2^{s-1}-1)/(2^s-1)$. For $s=2$, quadratic Greedy matches this bound; for fixed $s\ge3$, we give an online algorithm with prefix discrepancy $O(\log\log n+(\log T/\log n)^{1/2})$. In contrast, a deterministic algorithm that knows neither the horizon nor the failure probability keeps the terminal discrepancy $O_k(\sqrt{s}+\log\log n)$ at each prescribed time, with failure probability $n^{-k}$ for every fixed $k$, for $2\le s\le n/2$ (binary model) and $2\le s\le n$ (signed model); for $s=2$, quadratic Greedy itself does so. This answers their terminal question, and the same order is optimal for prefixes at all polynomial horizons $T\ge n$. The lower bound uses a finite safety game realized within the input law; the upper bounds use moments of elementary symmetric polynomials and, at terminal times, a $\cosh$ potential or a translated gauge with a Foster inequality at every state.

Comment
83 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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.78
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

Exact Universality of Online Discrepancy

cs.DS math.PR ·2026-09-08 ·Sunghyeon Jo, Taekyun Lee
theory similarity 0.71
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.45

The Online Steinitz Problem

cs.DS math.CO ·2026-10-12 ·Matteo Russo, Jiaye Wei
theory similarity 0.68
Abstract · 28 pages, 4 figures

Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem: $T$ vectors in $\mathbb R^d$, each of $\ell_2$-norm at most $1$ and with total sum zero, arrive one at a time and must be assigned immediately and irrevocably to unused positions of an array. The goal is to keep every prefix sum of the resulting order small. We first obtain deterministic prefix-discrepancy bounds of $O(\log T)$ for $d=1$ and $O(\sqrt T)$ for $d\ge2$. Our main contribution is a general reduction that converts deterministic and randomized online vector-balancing algorithms, which assign signs to arriving vectors, into online ordering algorithms. Combined with recent vector-balancing results, this yields a randomized algorithm with prefix discrepancy $O(\log T+\sqrt{d\log T})$ and running time $O(dT\log T)$. The guarantee holds with high probability against an oblivious adversary. The reduction also gives bounds for sparse vectors and extends to inputs in arbitrary compact convex bodies. Finally, we prove matching lower bounds in both the deterministic and randomized cases.

0.13

The Exact Online Threshold for the Asymmetric Binary Perceptron

cs.DS ·2026-09-02 ·Sunghyeon Jo, Taekyun Lee
highly cited similarity 0.66
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

Online balancing of vectors with small coordinates

cs.DM math.COcs.DSmath.PR ·2026-08-12 ·Antonios Hmadi
theory similarity 0.64
Abstract

Let $v_1,\ldots,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\|v_t\|_\infty\leqslant d^{-1/2}$ for some $d\geqslant 1$ and every $1\leqslant t\leqslant T$. There are absolute constants $L,C,c>0$ and a randomized online signing such that $$\mathbb{P}\left\{\max_{k\leqslant T}\left\|\sum_{t=1}^k\varepsilon_t v_t\right\|_\infty>6L\right\} \leqslant CT\exp\left(-\frac{cd}{\ln^2(ed)}\right).$$ Consequently, constant prefix discrepancy holds with probability at least $1-\varepsilon$ once $d$ is at least $C\ln\frac{3T}{\varepsilon}\left[\ln\left(e+\ln\frac{3T}{\varepsilon}\right)\right]^2$. In particular, every fixed sequence of vectors $a_t\in[-1,1]^m$ with at most $d$ nonzero coordinates admits an online signing with prefix discrepancy $O(\sqrt d)$ and failure probability at most $CT\exp[-cd/\ln^2(ed)]$. We also prove a nonuniform version in which the failure probability depends on the individual parameters $d_t=\|v_t\|_\infty^{-2}$, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$. We identify the corresponding $\ln^2 d$ barrier for the compact-potential method and extend the argument to general symmetric target bodies admitting a quadratic smoothness estimate.

0.38

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
theory similarity 0.64
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.29

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

cs.DS math.COmath.PR ·2026-11-05 ·Yuhao Lei
theory similarity 0.63
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.38

Online Algorithms Cannot Find Isolated Perceptron Solutions

cs.CC cs.DSmath-phmath.PR ·2026-11-02 ·Shuangping Li, Gabe Schoenbach
theory similarity 0.62
Abstract · 33 pages, 5 figures

The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor αn\rfloor$-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density $α> 0$, all but a vanishing fraction of solutions are isolated -- $Ω(n)$-far from all others, in Hamming distance. Such solutions are believed to be algorithmically inaccessible. Nevertheless, efficient algorithms find solutions at some constraint densities $α$. One possible resolution of this apparent contradiction is that the solution space also contains rare well-connected structures, and that algorithms succeed by locating them. Gong, Huang, Li and Sellke (FOCS 2026) proved this for stable algorithms, by showing that such algorithms cannot locate isolated solutions with probability more than $\approx 0.84$. In this work, we study online algorithms, which receive the columns of the constraint matrix one by one and sign each irrevocably upon arrival. This is a widely used class of algorithms in discrepancy minimization, and it includes the algorithm of Jo and Lee (2026), which has one of the best provable guarantees for the binary perceptron. We prove that at any constraint density, any online algorithm outputs an isolated solution with probability $o(1)$. Our proof is based on the observation that the signs an online algorithm has already fixed can be completed to at most one isolated solution, so a successful algorithm must choose the unique correct sign for each of the last few columns. Using the exchangeability of these columns, we show that such an algorithm must match a suffix-parallel baseline, which signs each of them as if it were the next column to arrive. We then use an anti-concentration argument to show that such a baseline rarely produces a unique completion.

0.30