The Precision Wall: An Optimizer-Dependent Boundary for Optimization under Power-Law Measurement Spectra

Lngel Kyo

cs.LGOct 29, 2026

The Precision Wall: An Optimizer-Dependent Boundary for Optimization under Power-Law Measurement Spectra

Authors: Lngel Kyo

Organizations: A2O Labs

Abstract

In low-rank matrix sensing of a rank- $D$ factor $U^\ast \in \mathbb{R}^{V \times D}$ , replacing isotropic Gaussian designs with power-law measurement covariance $Σ= \mathrm{diag}(j^{-s})_{j=1}^V$ leaves the Burer--Monteiro landscape free of spurious local minima, yet division-normalised first-order optimizers stall above a critical exponent $s^\ast$ . We trace this failure to a numerical precision wall. At the ground truth, the smallest non-gauge expected Hessian eigenvalue scales at leading order as $V^{-(s+1)}D^{-s}$ . When this curvature drops below the effective denominator floor $ε_O$ of optimizer $O$ , normalisation noise overwhelms rare-direction gradients, yielding the leading-order boundary $s^\ast_O(V, D) = [\log(1/ε_O) - \log V]/\log(VD) + δ_O$ , where $δ_O$ is a metric-dependent detection lag. With $δ_{\mathrm{Adam}}$ calibrated on four configurations and frozen, this formula predicts Adam's onset within $0.45$ across all 16 cells of a held-out grid ( $V \in \{64,128,256,512\} \times D \in \{4,8,16,32\}$ ), separates fixed- $VD$ pairs, and distinguishes denominator-precision walls from conditioning and sign-quantisation walls. The approximation fails at $D = 2$ , reflects a finite- $D$ spectral crossover, and saturates below $\varepsilon_0 = 10^{-8}$ at a dynamical floor.

Figures & tables

$V$	$D$	$m=1.5VD$	predicted $s^{\ast}$	empirical onset (rarest)	$\|\Delta\|$
8	4	48	5.20	5.21	0.01
16	8	192	3.71	3.70	0.01
32	8	384	3.18	3.19	0.01
16	4	96	4.25	4.23	0.02

Table 1: In-sample calibration of the precision wall for Adam (

\varepsilon_{0}=10^{-8}

60\text{k}

steps,

10

seeds per configuration,

s

-grid spacing

0.5

). Onsets measure where the rarest-direction relative error crosses

0.05

. Predictions use

s^{\ast}=[\log(1/\varepsilon_{0})-\log V]/\log(VD)+\delta_{\mathrm{Adam}}

with

\delta_{\mathrm{Adam}}=0.48

fitted to these four rows (in-sample RMS

0.013

, three residual degrees of freedom).

$V$	$D$	$VD$	predicted $s^{\ast}$	onset ( $\mathrm{rel}\text{-}d_{M}$ )	$\Delta$ ( $\mathrm{rel}\text{-}d_{M}$ )	onset (rarest)	$\Delta$ (rarest)
32	4	128	3.56	3.55	$-0.01$	3.34	$-0.228$
64	4	256	3.05	3.00	$-0.05$	2.98	$-0.07$
16	2	32	5.00	6.01	$+1.02$	5.71	$+0.711$
Fixed- $VD$ pairs ( $\delta_{O}$ cancels; a product-only law predicts $0$ for every pair):
pair		$VD$	pred. diff.	$\mathrm{rel}\text{-}d_{M}$ onsets & diff.		rarest diff.
$(32,4)$ vs. $(16,8)$		128	$-0.143$	3.55 vs. 3.84	$-0.29$	$-0.374$

Table 2: Out-of-sample validation on held-out configurations and fixed-

VD

pairs (

\delta_{\mathrm{Adam}}

frozen at

0.48

5

seeds,

60\text{k}

steps). Both the aggregate metric (

\mathrm{rel}\text{-}d_{M}>0.05

) and the rarest-direction metric (

|\Delta M_{VV}|/|M^{\ast}_{VV}|>0.05

, matching Table 1 ’s calibration definition) are reported from the same trajectories.

$V\setminus D$	$D=4$	$D=8$	$D=16$	$D=32$	$\rho(\Delta,D)$
$V=64$	$-0.036$	$-0.049$	$-0.070$	$-0.114$	$-1.0$
$V=128$	$-0.273$	$-0.251$	$-0.156$	$-0.108$	$+1.0$
$V=256$	$-0.070$	$-0.133$	$-0.221$	$-0.156$	$-0.8$
$V=512$	$-0.072$	$-0.165$	$-0.098$	$-0.216^{\dagger}$	$-0.8$

Table 3: Out-of-sample onset residuals

\Delta=s^{\ast}_{\mathrm{meas}}(\mathrm{rel}\text{-}d_{M})-s^{\ast}_{\mathrm{pred}}

across the pre-registered 16-cell Adam grid (

5

seeds,

60\text{k}

steps,

\varepsilon_{0}=10^{-8}

\delta_{\mathrm{Adam}}=0.482

frozen from Table 1 ). The rightmost column reports the row Spearman rank correlation

\rho(\Delta,D)

. Cell

(512,32)^{\dagger}

uses a float32-stored design instance with float64 arithmetic.

Figure 1: Per-direction relative error $\|(\Delta M)_{i,:}\|/\|M^{\ast}\|$ across spectral index $i$ for Adam at $\varepsilon_{0}=10^{-8}$ . At $s=0$ errors are uniform across coordinates; for $s\geq 3$ , error concentrates in the rarest directions (high $i$ ) by up to $25\times$ over common directions.

Figure 2: Ratio of rare-direction to common-direction residual error vs. exponent $s$ . Dotted vertical lines mark the predicted precision wall $s^{\ast}(V,D)$ from ( 6 ) at $\varepsilon_{0}=10^{-8}$ ; above $s^{\ast}$ , the ratio turns over as common directions also begin to degrade.

Figure 3: Recovery error $\mathrm{rel}\text{-}d_{M}$ at $60\text{k}$ steps across spectral exponent $s$ for eight optimizers at $(V,D)=(16,4)$ . Left: Three distinct failure regimes appear: sign-quantisation stall (SignSGD, Lion), conditioning stall (SGD, Momentum), and denominator-precision stall (Adam, RMSProp). Right: Division-normalised optimizers with vertical dotted lines marking the predicted walls $2.03$ ( $\varepsilon_{0}=10^{-4}$ ) and $4.25$ ( $\varepsilon_{0}=10^{-8}$ ).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

cell set	$n$	Law A: $(VD)^{-(s+1)}$	Law B: $V^{-(s+1)}D^{-s}$	Mid: $V^{-(s+1)}D^{-(s+1/2)}$
all exact cells	120	0.618	0.809	0.639
exact, $s\geq 4$	72	0.662	0.872	0.706
finite- $m$ direct ( $\lambda_{\min}/\lambda_{\max}>10^{-12}$ )	44	0.595	0.605	0.546
validation $(V,D)$ grid	25	0.299	0.184	0.221

Appendix

Table 4: Like-for-like three-parameter regression RMS in

\ln\lambda_{\min}^{\mathrm{ng}}

across spectral cell sets ( scripts/spectral_evidence.py

\to

data/spectral_evidence.json ).

The Loss Does Not See the Basis, but Adam Does
Aug 5, 2026Devender SinghLow-Rank Matrix Decomposition Matrix Optimization
Department of Computer Science Memorial University of Newfoundland
Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness
Oct 13, 2026Runze Shi, Ziye MaOverparameterization Matrix Factorization
City University of Hong Kong
The Spectral Dynamics and Noise Geometry of Muon
Jun 7, 2026Pierfrancesco Beneventano, Mahmoud Abdelmoneum, Tomaso PoggioMuon Optimizer Matrix Optimization
Massachusetts Institute of Technology

Aug 5, 2026J/K move · Enter open · S save

The Loss Does Not See the Basis, but Adam Does

Devender Singh

Department of Computer Science Memorial University of Newfoundland

Low-Rank Matrix Decomposition Matrix Optimization Adaptive Gradient Methods Matrix Factorization

Open paper AskPDF arXiv

Gradient descent on a factored model

W = UV^\top

is implicitly biased toward low-rank solutions, while Adam, starting from the same small initialization, is not. We trace the difference to the gauge symmetry of the loss, its invariance under

(U, V) \mapsto (UQ, VQ)

. Gradient flow's low-rank mechanism is available to an optimizer only if that optimizer is gauge-equivariant, a condition necessary for the transfer but not sufficient for low-rank recovery. Gradient descent, momentum, "shared-scalar" Adam, Muon, and Shampoo satisfy it. Adam, RMSProp, and the other coordinate-wise methods do not. A structure theorem characterizes the memoryless equivariant rules as exactly the Gram-determined left preconditioners, and a transfer theorem carries gradient flow's pathwise properties to common-scalar flows. We then sort nine update rules on underdetermined matrix sensing by recovery error against the planted ground truth. A one-parameter family from coordinate-wise to shared-scalar preconditioning restores the bias monotonically, isolating anisotropy as the cause. A "spectral schedule" reconciles two opposing reports about Muon: equal-rate updates recover exactly low-rank targets but lose their edge as the spectral tail grows. In transformers, Adam separates two gauge-equivalent initializations at the first step, where the equivariant optimizers stay at float precision, and ends with the per-head invariants

W_Q^\top W_K

56% apart in relative Frobenius distance, a gap no per-head rotation can close. On two hyperspectral datasets at matched training loss, gradient descent cuts held-out error by 43-44% at the lowest sampling density, and at lower effective rank. Basis choice is therefore not a tuning detail but a decision about which interpolant the optimizer selects.

Abstract

Explore similar work

The Loss Does Not See the Basis, but Adam Does

Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness

The Spectral Dynamics and Noise Geometry of Muon