CS Paper Radar

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

Lngel Kyo

cs.LG ·submitted 2026-10-29 17:14 UTC · v1

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.

Comment
19 pages, 3 figures, 4 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.70
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

Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

cs.LG ·2026-10-20 ·Yuxing Peng, Zhiqing Tang, Weijia Jia
theorycode/data similarity 0.59
Abstract · 60 pages, 2 figures, 1 table; Lean 4 formalization of the deterministic bounds: https://github.com/Pyx9876/zo-lower-bounds-lean (also in the…

Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding $\varepsilon$-stationary points of $L$-smooth nonconvex functions on $\mathbb{R}^d$ from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most $LE$; this is a fixed-matrix form of the effective rank condition used to explain zeroth-order fine-tuning. When $ET\le d$, the Gaussian two-point method that such fine-tuning uses needs only $O(ET)$ calls if it rejects steps that raise $f$, where $T=LΔ/\varepsilon^2$ is the iteration count of gradient descent from initial gap $Δ$, and we prove that every randomized method needs $Ω(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetildeΩ(d\min\{T,\sqrt{ET}\})$ calls, and adaptive subspace search attains $O(d\min\{T,\sqrt{ET}\})$: a deterministic method pays about $d$ calls per discovered direction, and the trace budget allows about $\sqrt{ET}$ directions. Determinism thus multiplies the cost by a factor of order $d/(E+\sqrt{ET})$ up to logarithmic factors, which grows linearly with $d$ for fixed $E$ and $T$; once $E$ exceeds $T$ by a logarithmic factor, deterministic methods need $Ω(dT)$ calls, as without any trace budget. Our lower bounds hold for $C^\infty$ functions with the matrix bound on all of $\mathbb{R}^d$, even when each call also returns gradient projections priced by rank.

0.23

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

cs.LG ·2026-11-07 ·Lngel Kyo
similarity 0.58
Abstract · 23 pages, 6 figures, 9 tables

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$.

0.27

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

cs.LG ·2026-09-03 ·Shi Fu, Huibo Xu, Qixin Zhang, Dacheng Tao
benchmark similarity 0.58
Abstract

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)^2$, where $w(A)$ is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension $d$, as $β\downarrow0$, the sharp worst-case sample complexity is $Θ(β^{-1}[d\log(1/β)+\log(1/δ)])$. The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with $O(1+\log(1/δ))$ samples, whereas an isotropic heavy-tailed design fails pathwise for $n\lesssim\sqrt{p/\log p}$. Gaussian smoothing yields an everywhere-positive $C^\infty$ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.

0.27

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

cs.DS math.PRmath.NAmath.ST ·2026-09-23 ·Yihan Zhang
similarity 0.58
Abstract

We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = λvv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(λ)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods with random initialization is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory.

0.18

Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements

cs.IT math.OCmath.ST ·2026-09-05 ·Andrew D. McRae
theory similarity 0.57
Abstract

We study the problem of low-rank matrix recovery from linear measurements via the global nonconvex landscape of a low-rank factored formulation of the matrix LASSO (nuclear-norm--regularized least-squares). If the landscape is benign, that is, has no bad local optima, then practical and scalable algorithms can compute good statistical estimates. Previous state-of-the-art landscape guarantees have typically assumed that the linear measurement operator has the restricted isometry property, that is, the operator is approximately an isometry over all low-rank matrices. This is an unrealistic assumption for many applications; in particular, when the individual measurement matrices are themselves low-rank, we typically have poor upper isometry constants. To overcome this, we establish new guarantees of a benign landscape under a weaker isometry condition: rather than requiring upper isometry over all low-rank matrices, we only require it over the linear low-rank tangent space to the low-rank ground truth matrix. To illustrate the utility of this result, we apply it to the problem of matrix recovery from random rank-one linear measurements; via high-probability concentration bounds on the random measurement operator, we prove a novel landscape guarantee with statistically near-optimal sample complexity and recovery error.

0.25

Geometry-Aware Score-Repellent Monte Carlo

cs.LG stat.ML ·2026-11-06 ·Jie Hu, Lingyun Chen, Do Young Eun
top venuetheory similarity 0.56
Abstract · To appear at NeurIPS 2026

The recently proposed Score-Repellent Monte Carlo (SRMC) method improves MCMC sampling by tilting the target density $π$ in $\mathbb{R}^d$ with the factor $\exp(-α\,θ_n^\top s(x))$, where the score function $s(x) = \nabla_x \log π(x)$, and $θ_n$ is the score average from past samples. However, a single scalar repellence strength $α\ge0$ cannot handle both the steep and the flat directions in anisotropic energy landscapes at once. We introduce \emph{Geometry-Aware SRMC} (GA-SRMC), which generalizes the Euclidean alignment to $θ^\top M s(x)$ for any symmetric positive-definite matrix $M$. A stochastic-approximation central limit theorem under a trace constraint on $M$ identifies the trace-normalized inverse Fisher $M_{\rm opt}\propto S^{-1}$ as the unique minimizer of the worst-direction covariance bound, elevating the Fisher information $S=\text{Cov}_π(s,s)$ from a proposal-side preconditioner (e.g., FisherMALA, natural gradient) to the bound-optimal repulsion-side matrix, with a single online estimate $\widehat S_n$ serving both roles at no additional computational cost. The full-Fisher online metric $M_n$ converges almost surely to $M_{\rm opt}$ and satisfies a CLT, providing a theoretical guarantee for the online implementation of the GA-SRMC framework. On an $8$-target simulation spanning the condition number $κ\in[1.3,100]$ and dimension $d\in[2,785]$, GA-SRMC dominates SRMC in ESS by $\boldsymbol{4.3\times}$ on anisotropic Gaussian ($κ=100$) and $\boldsymbol{6.8\times}$ on MNIST under the MALA baseline, by $\boldsymbol{16\text{--}32\%}$ on three well-conditioned logistic-regression posteriors, and by up to $\boldsymbol{+48\%}$ under FisherMALA; gains peak on the most anisotropic targets, and posterior-mean MSE is lower than with SRMC in all $16$ full-Fisher implementations.

0.33

Orthogonal Polynomial Approximation for Matrix Log Normalization in Global Covariance Pooling

cs.CV ·2026-08-19 ·Md Rifat Ur Rahman, Md Raihan Khan, Md Sakib Hossain Shovon, Pietro Liò, Mohammad Ali Moni
similarity 0.55
Abstract

Global Covariance Pooling (GCP) improves deep networks by capturing second-order feature statistics, and is especially effective for fine-grained recognition. Because covariance matrices live on the Symmetric Positive Definite (SPD) manifold, a normalization step is required before the Euclidean classifier. The faithful choice is the matrix logarithm (MLN-COV), which maps the SPD manifold to its tangent space; in practice it was abandoned in favour of the matrix square root because its eigendecomposition-based gradient is numerically unstable. We show that this instability is an artifact of computing the logarithm spectrally, not of the logarithm itself. Approximating the logarithm with finite polynomials in the covariance matrix removes the eigendecomposition from both passes: every operation becomes a General Matrix Multiplication (GEMM), the gradient stays bounded on the spectral support of the pre-normalized covariance, and the unstable 1/(lambda_i-lambda_j) term never appears. The key ingredient is a mean-eigenvalue pre-normalization that centres the spectrum near 1, away from the singularity of log, with a scalar post-compensation that returns the singular part of log(A) in closed form. Our recommended normalizer is a degree-8 Chebyshev expansion evaluated by a three-term matrix recurrence, with a matching reverse recurrence for the backward pass; Legendre, Laguerre, Taylor and Pade expansions are studied as controls that isolate the roles of the basis and of the target function. On three fine-grained benchmarks and ImageNet-1k the decomposition-free logarithm is both faster and more accurate than the spectral logarithm and than the square-root approximations it replaces, and at matched basis and degree the log target beats the square-root target, confirming that the gain comes from the faithful Riemannian map rather than from a better polynomial family.

0.37