PaperlayerView exact revision on arXiv

Source-linked AI summary

Stable and Online Algorithms for Random Matrix Discrepancy

Eren C. Kızıldağ, Shuangping Li

arXiv:2610.01591v1cs.DScs.CCcs.DMmath.COmath.PR

TL;DR

For random normalized GOE matrices in the proportional regime, the paper asks what density allows polynomial-time signings to meet a fixed operator-norm margin. It develops stable offline and online approaches, then identifies their distinct small-margin thresholds, both above the satisfiability scale.

  • Problem

    For iid normalized GOE matrices at N/d^2→τ, what density lets polynomial-time signing meet a fixed operator-norm margin, beyond merely guaranteeing that a signing exists?

    Source: §1 · p. 5

  • Method

    The paper combines stable recenter-and-round offline signing with online Frobenius-greedy signing, using rotational invariance to translate Frobenius control into operator-norm guarantees.

    Source: §2.2 · p. 14

  • Results

    Stable offline and online algorithmic thresholds scale as Θ(1/(κ^2 log(1/κ))) and Θ(κ^-2), respectively, both above the Θ(log(1/κ)) satisfiability scale.

    Source: §1 · p. 5

  • Takeaways & Limitations

    The small-margin density requirement depends on the algorithmic setting: stable offline algorithms require a lower scale than online algorithms, though both exceed satisfiability.

    Source: §1 · p. 5

    The exact satisfiability threshold for a fixed κ>0 remains open; the stated guarantee is asymptotic as κ↓0.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

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 $\kappa>0$, find signs $\sigma_1,\dots,\sigma_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N \sigma_i A_i$ is at most $\kappa\sqrt{N}$. Focusing on the proportional regime $N/d^2\to \tau\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $\kappa\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 $\tau=\Omega(\frac{1}{\kappa^2\log(1/\kappa)})$, 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 $\tau>\tau_{\rm FG}(\kappa)\sim \frac{\pi}{4\kappa^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: $\Theta(\frac{1}{\kappa^2\log(1/\kappa)})$ for stable offline algorithms and $\Theta(\frac{1}{\kappa^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $\Theta(\log(1/\kappa))$, as shown by Maillard~\cite{maillard2025}.

1 Introduction

The paper asks what density permits polynomial-time signings of random GOE matrices, and characterizes small-margin thresholds for stable offline and online algorithms. Its results separate algorithmic thresholds from the much lower satisfiability scale.

1 Introduction

  • General symmetric matrices lack a shared eigenbasis, making operator-norm balancing an infinite-direction problem rather than balancing d fixed coordinates.The operator norm requires controlling quadratic forms in every direction.Source: §1 · p. 4

1.1 Our results

  • Stable offline and online algorithmic transitions occur at Θ(1/(κ^2 log(1/κ))) and Θ(κ^-2), respectively, both above Maillard’s Θ(log(1/κ)) satisfiability scale.The paper studies the proportional regime N/d^2→τ and takes the small-margin limit after d→∞.Source: §1 · p. 5
  • No stable algorithm succeeds when τ≤c/[κ^2 log(1/κ)], regardless of running time.This lower bound matches the stable offline transition order.Source: §1 · p. 5, §1.1 · p. 6
  • Recenter-and-round balances Euclidean residual against expected sign flips in a strongly convex program, then applies independent mean-preserving rounding.Its analysis uses many columns with large positive projections in every direction to enable fractional cancellation and contract the residual.Source: §1.1 · p. 6
  • Frobenius-greedy runs in O(Nd^2), succeeds above τ_FG(κ)~π/(4κ^2), and every randomized online algorithm has exponentially small success probability when τ≤c/κ^2.The algorithm chooses each sign upon observing the corresponding matrix.Source: §1.1 · p. 6
  • Rotational invariance converts Frobenius-norm control into operator-norm guarantees, while the Frobenius-greedy analysis characterizes its full limiting performance curve.The analysis characterizes the radial evolution of the process.Source: §1.1 · pp. 6–7
  • After translating dimension-to-sign ratios, the offline and online transition scales match the corresponding small-margin algorithmic threshold orders for the symmetric binary perceptron.The paper also notes agreement of the satisfiability scales at leading order.Source: §1.1 · p. 7
  • The results complement an AMP analysis focused on small margins and provide, to the authors’ knowledge, the first sharp characterization of an online algorithmic threshold for random-arrival matrix discrepancy.The AMP work describes performance for a range of margins, while this paper pinpoints density requirements as κ↓0.Source: §1.1 · p. 8

2 Main Results and Technical Overview

This section presents the offline recenter-and-round and online Frobenius-greedy algorithms, along with their discrepancy guarantees and limiting performance. It develops the Frobenius-greedy analysis through a scalar radial fluid limit and establishes lower bounds for stable offline and online algorithms.

Round

  • For sufficiently small κ, recenter-and-round succeeds with high probability when τ ≥ C+/(κ^2 log(1/κ)).The theorem gives the asymptotic discrepancy guarantee as d tends to infinity; C+ is an absolute constant.Source: Round · p. 11

2.1 Offline algorithm: construction and stability

  • For every fixed α ≥ α0, recenter-and-round is noise-stable: correlated Gaussian inputs yield outputs close in normalized Hamming distance with high probability.The proof couples runs using the same initial signing and rounding uniforms, and establishes the guarantee uniformly for correlations sufficiently close to one.Source: Round · pp. 11, 13, 14
  • Recenter-and-round alternates fractional residual correction and mean-preserving randomized rounding, while rotational symmetry converts its Euclidean residual bound into an operator-norm guarantee.The objective controls residual size, expected flips, and uniqueness; the output residual has a rotationally invariant law, enabling the Euclidean-to-operator-norm conversion.Source: Round · pp. 10, 12, 13

2.2 Online Frobenius-greedy algorithm

Online Frobenius-greedy algorithm

  • For N/d^2 → τ, Frobenius-greedy succeeds whp if κ > Φ(τ) and fails whp if κ < Φ(τ); its threshold is specified for 0 < κ < 2.The performance curve is expressed using r(2τ), and the threshold is defined through the unique solution aκ to κ^2 = 2aκ^2 − aκ − log(1 − aκ).Source: Online Frobenius-greedy algorithm · p. 15
  • A scalar ODE determines Frobenius-greedy’s limiting performance curve, and rotational invariance converts its radial limit into an operator-norm limit.The analysis also establishes small-margin threshold asymptotics; the same ODE governs the second moment of the L2 mean-field optimal process studied by Fiedler, Jackson, Lacker, and Niles-Weed [FJLNW26, Section 7].Source: Online Frobenius-greedy algorithm · p. 16

2.3 Algorithmic lower bounds

  • For sufficiently small fixed κ, stable algorithms fail when τ ≤ 0.0053/(κ^2 log(1/κ)), making Algorithm 1 optimal up to constants in that regime.The lower bound also holds for a weaker finite-parameter stability notion described in the paper.Source: §2.3 · p. 16
  • For sufficiently small fixed κ, no online algorithm succeeds when τ ≤ C/κ^2 for a universal C > 0, matching Algorithm 2 up to constants.The ruled-out success probability is essentially sharp up to constants in the exponent compared with a fixed or input-independent random signing.Source: §2.3 · p. 17
  • The stable-algorithm lower bound uses an overlap-gap forbidden structure, stability across correlated instances, and a multi-color Ramsey argument.Small-ball bounds control feasible signings with overlaps in a narrow interval, yielding a contradiction after interpolation from one shared Gaussian instance to independent instances.Source: §2.3 · p. 17
  • The online lower bound fixes the signed prefix by conditioning on the random seed and first N − q matrices, then bounds all 2^q suffix signings by a union bound.Taking q of order κ^2N gives an exponentially small success probability and a density lower bound of order κ^-2.Source: §2.3 · p. 17

3 The Offline Algorithm: Guarantee and Stability

This section establishes the offline algorithm’s high-probability guarantee and noise stability by controlling its recentering and rounding rounds, bounding residual radii, and using rotational symmetry to obtain spectral control.

3 The Offline Algorithm: Guarantee and Stability

  • Proposition 3.1 establishes an asymptotic guarantee for Algorithm 1’s output when N/D converges to a sufficiently large constant.The proposition assumes a matrix with independent standard normal entries.Source: §3 · p. 17

3.1 Proof of Proposition 3.1

  • The proof works with iid Gaussian columns along a sequence where N/D converges to a fixed limit above a universal constant.The proof setup identifies the limiting aspect ratio as 2τ.Source: §3.1 · p. 18

Useful columns along every direction

  • Uniform cap coverage supplies useful columns in every direction, persists under Hamming perturbations, and implies fractional combinations contain a Euclidean ball of radius qt.The cap event holds with probability at least 1 − exp(−cαD); changing at most pN/8 signs leaves at least 3pN/8 useful columns per direction.Source: Useful columns along every direction · pp. 18–20

Gaussian norm bounds

  • Lemma 3.5 provides a high-probability event controlling the Gaussian matrix and its column norms, with failure probability at most e^-cD.The event is stated for fixed aspect ratio N/D→α with α≥2.Source: Gaussian norm bounds · p. 20

Proof of the recentering guarantee

  • A zero-residual feasible point certifies an upper bound on the recentering objective, whose minimizer trades residual size against flip cost and need not cancel exactly.The rounding analysis controls adaptive error at scale √(Dq) + D/t under its stated fixed-aspect-ratio conditions.Source: Proof of the recentering guarantee · pp. 20, 21, 23

One-step contraction and the global induction

  • A recenter-and-round step succeeds with probability at least 1 − Cα/D − e^-cαD when the current residual is at most 2BαDt, and scalar contraction supports the global induction.The scalar recurrence is bounded after logarithmically many iterations in its initial value.Source: One-step contraction and the global… · pp. 23–24
  • The induction preserves the radius and ceiling bounds at every round with high probability, yielding y_Kd ≤ A for a universal constant.The one-step contraction establishes the bounds simultaneously through all K rounds.Source: One-step contraction and the global… · p. 25

3.2 Proof of Theorem 2.2

  • For τ ≥ C+/(κ^2 log(1/κ)), the operator-norm bound is at most (C/√C+)κ, so sufficiently large universal C+ gives Theorem 2.2.Rotational invariance makes the residual direction uniform and independent of its radius, enabling the Euclidean-radius control to yield a spectral-norm guarantee.Source: §3.2 · pp. 25–26

3.3 Noise stability of recenter-and-round

  • The recentering analysis uses Gaussian geometry, but continuity of the quadratic program is deterministic; only final coordinatewise rounding is discontinuous, and it admits a canonical coupling.Source: §3.3 · p. 26

4 The Online Algorithm: Performance Guarantee

The section analyzes the Frobenius-greedy online algorithm by tracking its residual through a fluid limit and using rotational symmetry to obtain an operator-norm guarantee. It identifies the density threshold for success, while leaving the equality case unresolved.

4.1 Performance of the Frobenius-greedy algorithm

  • The fluid-limit argument separates the drift, which converges to an ODE solution, from a martingale term that vanishes as D grows.Source: §4.1 · pp. 29, 31
  • On bounded time intervals, the rescaled residual trajectory converges uniformly in probability to the unique ODE solution, giving R_N/√D→√y(2τ).Source: §4.1 · p. 32, §4.2 · p. 35
  • The update preserves rotational invariance, making the residual direction uniform and independent of its radius; this symmetry converts Frobenius-norm control into an operator-norm guarantee.Source: §4.1 · pp. 32–33

4.2 Density required for success

  • The algorithm succeeds with high probability when τ>τ_FG(κ), fails when τ<τ_FG(κ), and the equality case remains open.Source: §4.2 · p. 35

5 Hardness for Stable Algorithms

This section establishes the hardness result for stable algorithms by combining overlap restrictions with an interpolation and Ramsey argument. It also extends the hardness result to weaker finite-parameter stability assumptions.

5.1 The overlap-gap property

  • With high probability, no m feasible signings across the correlated instances and angle grid have all pairwise overlaps in [β − η, β].The theorem applies under its stated parameter assumptions and allows a finite angle set of size at most exp(γκN).Source: §5.1 · p. 37

Independent-input endpoint chaos

  • For independent endpoint instances, the first-moment estimate is exponentially small, yielding the endpoint-chaos claim by Markov’s inequality.The proof bounds the expected number of candidate tuples before applying Markov’s inequality.Source: Independent-input endpoint chaos · pp. 39–40

The finite interpolation and Ramsey construction

  • Adjacent outputs along each interpolation path have Hamming distance at most δN, enabling the stability step in the Ramsey construction.The proof establishes this bound for every path and consecutive grid pair on a high-probability event.Source: The finite interpolation and Ramsey… · p. 41

5.2 Proof of hardness for stable algorithms

  • The interpolation and Ramsey argument turns assumed success and stability into a clique contradicting endpoint chaos or ensemble multi-OGP.The proof uses a finite grid of correlated inputs, then applies Ramsey’s theorem to obtain a monochromatic clique.Source: The finite interpolation and Ramsey… · pp. 40–41

5.3 An alternative notion of stability

  • The hardness proof also applies under the weaker finite-parameter stability assumptions: for sufficiently large d, no algorithm is stable with the stated parameter tuple.The constants in the corollary depend only on the fixed parameters.Source: §5.3 · p. 42

6 Hardness for Online Algorithms

This section proves a lower bound for online algorithms by revealing a prefix and conditioning on it. The argument bounds the chance that any suffix signing completes a successful solution.

6 Hardness for Online Algorithms

  • For 0 < κ ≤ (8e)^−1/2 and τ ≤ 1/(10eκ^2), the proof establishes its stated strict lower-bound conclusion for online algorithms.The proof chooses c = (log 2)/(80τ) > 0 and obtains an exponentially small bound in N.Source: §6 · pp. 43–44
  • The proof takes q = ⌊ΔN⌋ with Δ = 4eκ^2, so q/N tends to Δ as d grows.For sufficiently large d, the chosen Δ lies in (0, 1/2) and 1 ≤ q < N.Source: §6 · p. 43
  • After conditioning on the revealed prefix, the suffix matrices remain independent, and a conditional union bound covers all 2^q possible suffix signings.The resulting bound holds for every online algorithm, regardless of how it chooses suffix signs.Source: §6 · pp. 43–44

Use of AI Tools

The authors report using AI models during manuscript preparation, including work related to the lower bounds and algorithms. They take responsibility for the mathematical content and correctness of the final text.

Use of AI Tools

  • The authors report using GPT-5.6 and GPT-6, in Pro and Astra modes, during manuscript preparation.They state that the algorithmic lower bounds were established by the authors and later simplified by AI.Source: Use of AI Tools · p. 44
  • The authors say conversations with AI helped produce the matching algorithms and the rotational-symmetry idea for converting small Euclidean residuals to operator-norm bounds.They particularly identify the recenter-and-round algorithm as arising from this work.Source: Use of AI Tools · p. 44
  • The authors take full responsibility for the mathematical content and correctness of the final text.Source: Use of AI Tools · p. 44

Related papers

Loading 2610.01591v1…