cs.LGNov 7, 2026

Breaking Precision Walls in First-, Second-, and Zeroth-Order Optimizers: One Constant, Set in Advance

Authors: Lngel Kyo

Organizations: A2O Labs

Abstract

Under power-law signal decay across directions, an optimizer can fit strong directions and miss weak ones while average loss hides it. A precision wall measures the steepest decay where the weakest direction recovers within 5% in a fixed budget. On low-rank matrix sensing and quadratics one constant sets the wall: once it dominates the denominator, Adam or grafted Shampoo is momentum descent at step η/cη/c, setting the wall; in Shampoo, matching grafting's constant to damping restores the wall after three hypotheses failed. In zeroth-order Adam, ε\varepsilon acts against ε∗\varepsilon^\ast from a mean-square spectral model; below ε∗\varepsilon^\ast error hits a noise floor. Set from true curvature or spectrum on new shapes, the rule raised the wall above the same-step default by a forecast amount: on two sensing shapes by 1.96,1.151.96, 1.15 (Adam) and 1.59,1.741.59, 1.74 (grafted Shampoo), and on two Hadamard-rotated quadratics by 1.12,0.731.12, 0.73 (zeroth-order Adam, longer budget), rising on all seeds; fixed-step momentum at that step reaches those walls. A cosine-scheduled default (small constant giving weak modes large steps) is higher on one sensing shape, matched on new seeds of the other, and lower with the rule's constant. A default step retuned per budget catches up on rotated quadratics and population logistic regression, fails at 1 query/step on two diagonal quadratics (catching up at 16), and exceeds the rule on digits logistic regression (full-batch and minibatches, where gradient noise sets the η=0.01,0.1η= 0.01, 0.1 default walls). On logistic regression the rule did not raise the first-order wall: same-step default Adam was higher (its wall on 4 new shapes at the forecast stability limit), while in zeroth order on the population loss setting ε\varepsilon raised the wall by 0.98,0.880.98, 0.88.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 29, 2026

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

In low-rank matrix sensing of a rank-DD factor U∗∈RV×DU^\ast \in \mathbb{R}^{V \times D}, replacing isotropic Gaussian designs with power-law measurement covariance Σ=diag(j−s)j=1VΣ= \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∗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−sV^{-(s+1)}D^{-s}. When this curvature drops below the effective denominator floor εOε_O of optimizer OO, normalisation noise overwhelms rare-direction gradients, yielding the leading-order boundary sO∗(V,D)=[log⁡(1/εO)−log⁡V]/log⁡(VD)+δOs^\ast_O(V, D) = [\log(1/ε_O) - \log V]/\log(VD) + δ_O, where δOδ_O is a metric-dependent detection lag. With δAdamδ_{\mathrm{Adam}} calibrated on four configurations and frozen, this formula predicts Adam's onset within 0.450.45 across all 16 cells of a held-out grid (V∈{64,128,256,512}×D∈{4,8,16,32}V \in \{64,128,256,512\} \times D \in \{4,8,16,32\}), separates fixed-VDVD pairs, and distinguishes denominator-precision walls from conditioning and sign-quantisation walls. The approximation fails at D=2D = 2, reflects a finite-DD spectral crossover, and saturates below ε0=10−8\varepsilon_0 = 10^{-8} at a dynamical floor.
Nov 1, 2026

A Self-Generated Floor on Adam's ε\varepsilon: Evidence from Power-Law Matrix Sensing

In nonconvex Burer--Monteiro low-rank matrix sensing of U∗∈RV×DU^\ast \in \mathbb{R}^{V \times D} under power-law covariance Σ=diag(j−s)j=1VΣ= \mathrm{diag}(j^{-s})_{j=1}^V, the precision-wall approximation predicts that Adam stalls when the smallest non-gauge Hessian eigenvalue drops below its denominator floor, giving s∗(V,D)=[log⁡(1/εeff)−log⁡V]/log⁡(VD)+δAdams^\ast(V,D) = [\log(1/\varepsilon_{\mathrm{eff}}) - \log V]/\log(VD) + δ_{\mathrm{Adam}}. If εeff\varepsilon_{\mathrm{eff}} were set by ε0\varepsilon_0, lowering ε0\varepsilon_0 from 10−1010^{-10} to 10−1210^{-12} would raise s∗s^\ast by 0.95–1.330.95\text{--}1.33. Instead, across six values of ε0\varepsilon_0 two decades apart, 10−210^{-2} to 10−1210^{-12}, the boundary follows the ε0\varepsilon_0 slope down to 10−610^{-6}, bends near 10−810^{-8}, and is flat below 10−810^{-8}, while warm-started L-BFGS and Gauss--Newton reach machine precision on stalled instances. We trace this saturation to a self-generated dynamical floor εdyn∝α\varepsilon_{\mathrm{dyn}} \propto α: high-curvature modes oscillate persistently near the adaptive edge of stability with amplitude ∝α(1−β1)/(1+β1)\propto α(1-β_1)/(1+β_1) and leak gradient fluctuations of scale κακα into rare modes via measurement coupling, pinning v^V≈κα≫ε0\sqrt{\hat{v}_V} \approx κα\gg \varepsilon_0. Fitting a single threshold-crossing wall parameter εdyn=4.76×10−9\varepsilon_{\mathrm{dyn}} = 4.76\times 10^{-9} (with the detection lag frozen at its companion calibration) predicts the saturated failure boundary for D≥4D \ge 4 across five (V,D)(V,D) scales to RMS 0.0980.098 (breaking down at D=2D = 2), while shrinking ε0\varepsilon_0 below 10−810^{-8} is ineffective and lowering the step size αα reduces the floor directly.
Aug 5, 2026

The Loss Does Not See the Basis, but Adam Does

Gradient descent on a factored model W=UV⊤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)↦(UQ,VQ)(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 WQ⊤WKW_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.