Stable and Online Algorithms for Random Matrix Discrepancy
Abstract
We study the average-case matrix discrepancy problem: given independent normalized d× d Gaussian orthogonal ensemble matrices A1,…,AN and a fixed margin κ>0, find signs σ1,…,σN∈{−1,1} such that the operator norm of ∑i=1N σi Ai is at most κ√N. Focusing on the proportional regime N/d2→ τ∈(0,∞) as d→∞ followed by the small-margin limit κ↓ 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 τ=Ω(1/κ2log(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 τ>τFG(κ)∼ π/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: Θ(1/κ2log(1/κ)) for stable offline algorithms and Θ(1/κ2) for online algorithms. Both thresholds lie far above the satisfiability scale Θ(log(1/κ)), as shown by Maillard~\cite{maillard2025}.
Related
- Free-Probabilistic State Evolution and Random Matrix Discrepancy
- Online Discrepancy of Sparse Random Vectors over Long Horizons
- Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
- Exact Universality of Online Discrepancy
- Online Discrepancy for Sub-Exponential Product Distributions via Regularization
BibTeX
@misc{kızıldag2026stable,
title = {{Stable and Online Algorithms for Random Matrix Discrepancy}},
author = {Eren C. Kızıldağ and Shuangping Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01591},
eprint = {2610.01591},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01591},
}
RIS
TY - UNPB
TI - Stable and Online Algorithms for Random Matrix Discrepancy
AU - Eren C. Kızıldağ
AU - Shuangping Li
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01591
UR - https://arxiv.org/abs/2610.01591
AB - We study the average-case matrix discrepancy problem: given independent normalized d× d Gaussian orthogonal ensemble matrices A_1,…,A_N and a fixed margin κ>0, find signs σ_1,…,σ_N∈{−1,1} such that the operator norm of ∑_i=1^N σ_i A_i is at most κ√N. Focusing on the proportional regime N/d^2→ τ∈(0,∞) as d→∞ followed by the small-margin limit κ↓ 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 τ=Ω(1/κ^2log(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 τ>τ_FG(κ)∼ π/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: Θ(1/κ^2log(1/κ)) for stable offline algorithms and Θ(1/κ^2) for online algorithms. Both thresholds lie far above the satisfiability scale Θ(log(1/κ)), as shown by Maillard~\cite{maillard2025}.
ER -