CS Paper Radar

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

Lngel Kyo

cs.LG ·submitted 2026-11-07 13:43 UTC · v1

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$, 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.15$ (Adam) and $1.59, 1.74$ (grafted Shampoo), and on two Hadamard-rotated quadratics by $1.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$ 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.88$.

Comment
23 pages, 6 figures, 9 tables

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG ·2026-11-01 ·Lngel Kyo
similarity 0.63
Abstract · 23 pages, 3 figures, 5 tables

In nonconvex Burer--Monteiro low-rank matrix sensing of $U^\ast \in \mathbb{R}^{V \times D}$ under power-law covariance $Σ= \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^\ast(V,D) = [\log(1/\varepsilon_{\mathrm{eff}}) - \log V]/\log(VD) + δ_{\mathrm{Adam}}$. If $\varepsilon_{\mathrm{eff}}$ were set by $\varepsilon_0$, lowering $\varepsilon_0$ from $10^{-10}$ to $10^{-12}$ would raise $s^\ast$ by $0.95\text{--}1.33$. Instead, across six values of $\varepsilon_0$ two decades apart, $10^{-2}$ to $10^{-12}$, the boundary follows the $\varepsilon_0$ slope down to $10^{-6}$, bends near $10^{-8}$, and is flat below $10^{-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 $\varepsilon_{\mathrm{dyn}} \propto α$: high-curvature modes oscillate persistently near the adaptive edge of stability with amplitude $\propto α(1-β_1)/(1+β_1)$ and leak gradient fluctuations of scale $κα$ into rare modes via measurement coupling, pinning $\sqrt{\hat{v}_V} \approx κα\gg \varepsilon_0$. Fitting a single threshold-crossing wall parameter $\varepsilon_{\mathrm{dyn}} = 4.76\times 10^{-9}$ (with the detection lag frozen at its companion calibration) predicts the saturated failure boundary for $D \ge 4$ across five $(V,D)$ scales to RMS $0.098$ (breaking down at $D = 2$), while shrinking $\varepsilon_0$ below $10^{-8}$ is ineffective and lowering the step size $α$ reduces the floor directly.

0.26

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

cs.LG ·2026-10-29 ·Lngel Kyo
similarity 0.58
Abstract · 19 pages, 3 figures, 4 tables

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.

0.56

Beyond Quadratic Loss: The Stability Phase Diagram of Adam

cs.LG math.OCstat.ML ·2026-09-16 ·Gaoxiang Tang, Huanran Chen, Ziming Liu
similarity 0.54
Abstract · 21 pages, 9 figures

Loss spikes are recurrent instabilities in neural-network training and can arise from multiple mechanisms. For Adam in particular, macroscopic loss spikes have been linked to optimizer dynamics, yet how its two momentum timescales govern them remains unclear. We investigate this dependence by mapping training dynamics across the $(β_1,β_2)$ plane. Across a range of model--task settings, an approximately linear boundary, $1-β_2=C(1-β_1)$, separates spiky from non-spiky dynamics, whereas a one-dimensional quadratic loss produces approximately cubic slope. A one-dimensional superquadratic loss $L(x)\propto|x|^n$ recovers the near-linear scaling and links the boundary coefficient to the effective loss exponent $n$. We further show that confident cross-entropy losses develop a core--wall landscape comprising a narrow quadratic core followed by a steep wall, which produces effective superquadratic behavior at the scale of an optimizer update. Together, these results connect Adam loss spikes to both the mismatch between momentum timescales and finite-scale superquadratic loss geometry beyond the Hessian.

0.23

Optimizer Geometry Sets the Pace: Spectral Learning Dynamics in Matrix Factorization

cs.LG ·2026-10-03 ·Mahalakshmi Sabanayagam, Simon Lucey
similarity 0.54
Abstract · Under review

Recent successes of matrix- and curvature-based optimizers have renewed interest in how update geometry shapes learning. These methods normalize or precondition updates, changing how different components progress during training. In deep matrix factorization, the geometry that slows gradient descent (GD) favors low-rank solutions by delaying the emergence of small singular modes. This raises the question of what remains of that spectral bias when normalization or curvature correction weakens or removes the slowdown. We study how optimizer geometry and depth jointly govern this behavior through a common framework for singular mode dynamics. Under explicit balance and alignment assumptions, we derive birth, saturation, and decay laws for Euclidean GD, coordinate-wise updates of SignGD and an instantaneous Adam approximation, spectral updates of Muon and cumulative Shampoo, and a block curvature model of K-FAC. The resulting picture is not a simple ordering from stronger to weaker low-rank bias. To highlight, SignGD and ideal Muon eliminate the divergent birth barrier and drive unsupported modes to zero in finite time. Cumulative Shampoo initially retains GD's depth-dependent barrier, then accumulated gradients produce a catch-up phase while making previously active modes increasingly persistent. Undamped K-FAC cancels the factorization-induced slowdown while preserving the ordering of the target singular values, whereas positive damping introduces a spectral threshold below which the slow GD phase laws reappear. These results give normalization, accumulated state, damping, and depth a direct interpretation as controls determining when modes emerge, persist, and disappear during training.

0.39

When Do Rankings Beat Signs? Gradient Direction Recovery under Even Nuisance

cs.LG ·2026-11-19 ·Zhuangzhuang Pan, Yan Xia, Chee Seng Chan
theoryunusual similarity 0.54
Abstract · 51 pages, 7 figures, 14 tables, including appendices

Can ranking a batch of antipodal query pairs recover a gradient direction with fewer evaluations than using within-pair signs alone? We study fixed-center recovery in $d$ dimensions for a linear signal plus an unknown differentiable even nuisance, counting function evaluations and feedback rounds separately. Shared pair offsets create an information hierarchy: Mirror retains within-pair signs, Reverse couples reversed cross-pair orders to cancel offsets, and Full enforces all ranking inequalities. Relative shell variation is the nuisance range over the query sphere normalized by the linear-signal scale. When it is at most $c\varepsilon/\sqrt{d}$, Reverse localizes every consistent direction to angular accuracy $\varepsilon$ using $\widetilde{O}(d+\sqrt{d/\varepsilon})$ evaluations in one round at fixed confidence, without a variation bound supplied to the decoder. This matches a lower bound up to logarithmic factors, versus the $Θ(d/\varepsilon)$ one-round sign-only minimax cost on the same class. Over well-conditioned positive-definite quadratics with no common relative-curvature bound, the $R$-round minimax cost is instead $Θ(dR(\varepsilon^{-1/R}-1))$, even with cumulative rankings. We extend validity beyond exact evenness under supplied error bounds. Matched-endpoint experiments certify information beyond signs and short cycles. On two ridge tasks under joint evaluation and round caps, short-cycle recovery attains lower terminal mean gaps than the tested batch-capable controls. An additional optimization benefit from fitting the complete ranking remains unestablished.

0.31

Why Adaptive Optimizers Underestimate Rare Tokens

cs.LG stat.ML ·2026-09-29 ·Sangsidhya Kar
similarity 0.53
Abstract

In the softmax output layer, a rare token receives a small positive logit gradient on most steps and a much larger negative gradient on the few steps when it is the target. SGD simply adds these contributions. Coordinate-wise adaptive methods such as Adam, RMSProp, and sign descent instead divide each update by a running estimate of its magnitude, and that estimate is largest immediately after the token appears. This imbalance has two effects. At the level of the whole output layer, we characterize which optimizers preserve the mean output embedding: every method whose update is linear in past gradients does, as do Kronecker-factored and orthogonalized methods such as Shampoo and Muon. Adam, Adafactor, Lion, and sign descent do not, and for these methods we obtain an exact step-by-step expression for the change. At the level of an individual rare token, the same normalization shifts the training fixed point. In the unigram model, sign descent lowers the logit of every token that occurs in fewer than half of the minibatches at a constant expected rate. For RMSProp with periodic arrivals, we can solve the fixed point in closed form: if a token is absent for at least two consecutive minibatches, its equilibrium probability is strictly below its data frequency for every learning rate, and the ratio tends to $κ/(2(e^{κ/2}-1))$. Here $κ$ is the mean number of steps between occurrences divided by the second-moment time constant $1/(1-β_2)$. In the same model, SGD and AMSGrad retain the unbiased fixed point. We test these predictions both in a unigram model and in a small language model trained from a known generating distribution. With random arrivals, the bias is larger than the periodic formula predicts; in the language model, the optimizers with the biased fixed point also fit the generating distribution less well.

0.32

Gradient-Update Mismatch: Rethinking Conflict-Free Training of Physics-Informed Neural Networks

cs.LG ·2026-09-01 ·Jing Xiao, Xinhai Chen, Qinglin Wang, Menghan Jia, Zhiquan Lai +3 more
code/data similarity 0.52
Abstract

Training Physics-Informed Neural Networks (PINNs) requires jointly optimizing physics residual and initial/boundary condition loss terms, which often induce conflicting gradients. Gradient surgery methods mitigate this issue by constructing directions from loss-specific gradients to reduce conflict before optimizer transformation. However, even when the constructed direction is conflict-free, this property may not be preserved after optimizer transformation. Let $a_t$ denote the direction constructed by gradient surgery, $u_t$ the optimizer proposal, and $\mathcal{C}_t$ the conflict-free cone induced by the loss-specific gradients. We show that modern optimizers can transform $a_t$ through mechanisms such as historical state, adaptive scaling, preconditioning, or decoupled weight decay, so $a_t \in \mathcal{C}_t$ does not generally imply $u_t \in \mathcal{C}_t$. We refer to this optimizer-induced discrepancy in conflict-freeness between $a_t$ and $u_t$ as Gradient-Update Mismatch (GUM). Accordingly, we propose Gradient-Update Alignment (GUA), which projects $u_t$ onto $\mathcal{C}_t$ to obtain the aligned update $p_t$ and applies $p_t$ to the parameters. When the optimizer maintains internal state, GUA further adjusts this state toward targets reconstructed from the applied update. We conduct extensive experiments and find that GUM is widespread across momentum, adaptive, and curvature-based optimizers, with conflict rates reaching up to 86.3%. Across all PINN settings, GUA achieves conflict-free applied updates and consistently improves various gradient surgery methods, reducing the relative $L_2$ error by up to 98.2% in individual settings. Data and code are available at https://github.com/JingXiao10/GUA.

0.50

Muon Operates Beyond the Edge of Stability

cs.LG ·2026-10-16 ·Niko Covic, Baraq Lipshitz, Alexander Padula, Stefan Visnjic
code/data similarity 0.52
Abstract

We study the Muon optimizer using sharpness and provide the first empirical evidence that the Flat Minima Hypothesis also applies to Muon. Further, we derive Muon's implicit preconditioner to analyze its potential Edge of Stability behavior. Experiments on CIFAR-10 show sharpness strongly correlates with generalization gap within each optimizer (Pearson $r = 0.45$-$0.69$, $p \leq 10^{-4}$), confirming the hypothesis holds for Muon similarly to Adam and SGD. However, Muon operates above the classical sharpness-based Adaptive Edge of Stability threshold that bounds diagonally-preconditioned optimizers like Adam and RMSprop, yet remains stable. Our findings suggest Muon operates in a fundamentally different regime than diagonally-adaptive methods. Defining the exact stability boundary for Muon remains an open question. All code is available at https://github.com/NikoCovic/DL-project.

0.24