CS Paper Radar

Gauss-Newton Accuracy and Indefinite Hessians: Uniform Coexistence in Low-Cost Sets

Kihun Rhee, Hanjoon Byun

cs.LG stat.ML ·submitted 2026-10-07 08:38 UTC · v1
theory

Abstract

We study the accuracy of Gauss-Newton curvature in ridge-regularized nonlinear least squares. Under local regularity and persistence of level-set curvature magnitude along an exact-fit section, we prove uniform coexistence of two curvature regimes. Global minimizers exist, and every global minimizer has relative Hessian error below $(1+\sqrt2)/8$, while the same low-cost set contains a point with an indefinite Hessian and relative error at least $15/8$. One positive ridge cap works for all independent center and label perturbations in fixed neighborhoods and every positive ridge weight up to the cap. These neighborhoods do not shrink as the ridge weight tends to zero. A pointwise certificate based on the current prediction level set controls the normal, mixed, and tangent parts of the Hessian correction. We prove a sharp relative-error bound over the stated pointwise class when the prediction map and ridge vary. Analytic examples describe the roles of output alignment, curvature orientation, and persistence. A separate structural result gives full Jacobian row rank throughout low-cost sets and exact interpolation near a rank-deficient reference.

Comment
28 pages, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

Explaining f-Divergence-Based Regularization via Local Curvature and Sharpness-Aware Minimization

cs.LG cs.IT ·2026-09-08 ·Nour Jamoussi, Marios Kountouris
publishedbenchmark similarity 0.63
Abstract · Published at 5th Conference on Lifelong Learning Agents (CoLLAs), 2026

Divergence-based regularization and Sharpness-Aware Minimization (SAM) are two prominent approaches for improving generalization in deep learning, both motivated by robustness to perturbations. However, their relationship has remained largely unexplored. Building on classical second-order expansions of $f$-divergences, we show that the two methods are locally consistent under parameter-space perturbations: both induce curvature-sensitive penalties, with divergence regularization yielding a Fisher-weighted quadratic form and SAM penalizing sharpness through the dominant Hessian eigenvalue. For negative log-likelihood objectives with exponential-family output distributions, this correspondence becomes especially transparent, since the Fisher and Gauss-Newton matrices coincide. We further show that the same local geometric perspective extends to input-space perturbations, where divergence-based regularization is defined through transformations of the input. In this setting, the regularizer induces a pullback quadratic form on the input space, providing a more general perturbation framework than standard SAM while preserving the same local sensitivity interpretation. To validate the analysis empirically, we use the asymmetric $α$-skew Jensen-Shannon divergence (JSD) family as a controlled testbed. Its local curvature coefficient scales as $α(1-α)$ and is maximized at the symmetric point $α=\tfrac12$, which recovers the standard JSD. Loss-landscape visualizations in the input-perturbation regime show that stronger induced curvature penalization is associated with flatter local minima. Experiments on four benchmark datasets further demonstrate that both accuracy and negative log-likelihood are consistently best near this regime of maximal curvature penalization.

0.57

Calibrated Target Noise Recovers Curvature from the Gradients

cs.LG ·2026-11-05 ·Arash Jamshidi, Katsiaryna Haitsiukevich, Aristides Gionis, Kai Puolamäki
top venue similarity 0.62
Abstract · Accepted at NeurIPS 2026. 39 pages

Estimating curvature information from gradients alone is a fundamental problem in machine learning. The challenge becomes particularly acute in settings where only aggregate mini-batch gradients are available, yet curvature information is still required for applications such as preconditioning in optimisation, sampling, and early stopping. Perhaps surprisingly, we show that a simple target-perturbation scheme suffices to recover such curvature information from gradients alone. Our method injects zero-mean noise into the targets, with variance calibrated to the local output curvature. The covariance of the resulting noisy batch gradients then recovers practical curvature matrices, without requiring per-sample gradients, second-order derivatives, or other internal network quantities. For a broad class of non-linear models, our scheme recovers the Generalised Gauss--Newton (GGN) matrix; for feed-forward ReLU networks, it additionally recovers the diagonal blocks of the population Hessian. We demonstrate that the resulting estimator is simple, lightweight, provably optimal, and easy to integrate into existing training pipelines. Experiments demonstrate accurate curvature recovery, faster optimisation when the estimator is used for preconditioning, and the utility of the estimated GGN for early stopping.

0.31

Affine-invariant Cubic Newton with Weak Learners

cs.LG stat.MLmath.OC ·2026-10-24 ·Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon
top venue similarity 0.59
Abstract · Accepted to 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global $\mathcal{O}(1/γ^{12}k^2)$ rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy $γ^{12}$ dependence on a worst-case `weak gradient edge' $γ$. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values $\overlineΘ_k$ along the optimization path and directional improvements $δ_k$ in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by $δ_k$. Under semi-strong self-concordance, we establish a global $\mathcal{O}(1/\overlineΘ_k^4 k^2)$ rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.

0.34

One Size Does Not Fit All: Curvature-Aware Adaptive Perturbation for SAM

cs.LG cs.AI ·2026-10-14 ·Alessia Rossi, Felipe Campelo, Gabriel L. Oliveira
theory similarity 0.59
Abstract

Poor generalisation in deep neural networks is frequently associated with convergence to sharp minima. Sharpness-Aware Minimisation (SAM) improves generalisation of deep neural networks by minimising a combination of the training loss and the local sharpness of the loss landscape, biasing convergence towards flat minima. However, SAM relies on a fixed perturbation radius $ρ$ that ignores local curvature, leading to inefficient behaviour: the perturbation may be too small to escape poor basins defined by sharp local minima, or too large to allow convergence to solutions with good loss-sharpness tradeoff. We reinterpret $ρ$ as the intensity of the perturbation signal and propose Curvature-Aware Adaptive Perturbation for SAM (CAP-SAM), a geometry-aware method that modulates the perturbation radius based on a sharpness ratio, enabling a more effective search for robust minima on the loss landscape. We prove that CAP-SAM preserves the same convergence rate as standard SAM in non-convex stochastic settings. Extensive experiments indicate that our approach consistently outperforms SAM and its most prominent variants across diverse network architectures on CIFAR-10, CIFAR-100, and ImageNet.

0.21

The Road Taken: The Role of Optimizers at the Edge of Stability

cs.LG ·2026-08-19 ·Jaerin Lee, Kyoung Mu Lee
similarity 0.58
Abstract · 34 pages, 13 figures, fixed typo

The edge of stability refers to a phenomenon in deep learning with gradient-based optimizers where the Hessian eigenvalues of the loss remain stable above a threshold that the classical descent lemma predicts to be unstable. Previous works formulate the edge of stability with respect to the maximum Hessian eigenvalue and the learning rate. However, we observe that many first-order methods, including gradient descent, significantly violate the stability bound predicted by these theories by a factor as large as $\times 21.1$. Moreover, this deviation turns out to be systematic and highly dependent on the underlying optimizer, which is not captured by previous formulations. This calls for a new formulation of the stability threshold, which we derive from the directional Hessian and the gradient-alignment score with respect to the actual update taken by the optimizer, rather than the maximum curvature mode. Our new formulation of the realized edge of stability not only removes optimizer-dependent offsets and provides more consistent predictions of the stability threshold, but also introduces new diagnostic tools that reveal the unique role of the optimizer in actively balancing between the temporal and spatial budgets in first-order optimization.

0.37

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

Riemannian Difference-of-Convex Optimization for K-Means Clustering

cs.LG math.OC ·2026-09-28 ·Meng Xu, Bo Jiang, Hanfu Zhang, Ya-Feng Liu, Anthony Man-Cho So
similarity 0.57
Abstract · 5 pages

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an $ε$-Riemannian critical point within $O(ε^{-3})$ iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

0.13

Extrinsic Curvature Estimation by Closest Point Projection of Rays

cs.CG math.DG ·2026-10-24 ·Liangchen Liu, Yen-Hsi Richard Tsai
similarity 0.57
Abstract · 45 pages, 9 figures

We propose a parametrization-free framework for estimating the second fundamental form and the principal curvatures of a submanifold of $\mathbb{R}^d$. The method uses the closest point projections of a few short random rays and recovers the curvature from the curves that these projections induce on the submanifold, without coordinate charts or local fitting. We analyze the geometry of the induced curves and characterize when they are geodesics. For hypersurfaces, these results give two algorithms with error bounds: a least squares reconstruction of the second fundamental form from the curvatures of the induced curves, and a direct estimate of all principal curvatures from the eigenvalues of a $d\times d$ matrix built from $d$ rays, which needs no normal information and costs $\mathcal{O}(d^3)$ besides the projections. In higher codimension, we can also recover the second fundamental form one normal direction at a time. On point clouds, where the projection becomes a nearest neighbor query, we bound the additional error. Experiments confirm the predicted rates for hypersurfaces in up to $128$ dimensions, for surfaces of codimension up to $98$, and on point clouds, demonstrating the effectiveness of the proposed framework in practice.

0.33