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

Kihun Rhee; Hanjoon Byun

cs.LGOct 7, 2026

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

Authors: Kihun Rhee, Hanjoon Byun

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.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Sufficient test	Required information	Guarantee	At Proposition 6 ’s point
Full residual norm [ 9 , Proposition 5]	$\left\\|E\right\\|<\lambda$ , with ridge and residual correction in the same normalization.	Positive full Hessian with margin $\lambda-\left\\|E\right\\|$ .	Fails: $\left\\|E\right\\|/\lambda=1/(16a)\geq 4$ .
Distance tube [ 4 , Lemma E.1]	Source Assumptions 1 and 3: a compact minimizer manifold, local PL regularity, negative-definite Hessians at exterior critical points, and a bounded third derivative on a tube. The point must lie within the stated or proof-refined radius.	$H\succeq\lambda I/2$ inside that sufficient tube.	Fails both radii: $\operatorname{dist}/r_{\rm refined}>3/(8a)$ .
Pointwise directional test Theorem 2	Cost, Jacobian rank, second-derivative bound, and the tangent curvature gate ( 7 ).	$H\succeq\lambda I/2$ and the relative bound in Corollary 3 .	Passes with $C=1/512$ , $s=1$ , $M=2$ .

Appendix

Table 1: Comparison of specified sufficient conditions. Failure of a row’s test is not failure of every method in the cited work. The example also admits a directional cost-only check if its observed cost is used; it does not show that gradient information is necessary.

Explore similar work

Generalization in Nonlinear Least Squares via Learned Feature Geometry
Jun 7, 2026Ayub Kharel, Ilja Kuzborskij, Patrick Rebeschini +1Generalization Bounds Least Squares
University of Oxford · Google DeepMind · Sapient Intelligence
Error whitening: Why Gauss-Newton outperforms Newton
May 11, 2026Maricela Best McKay, Nathan P. Lawrence, Brian Wetton +1Newton Whitening
University of British Columbia · University of California, Berkeley
Curvature-Weighted Gradient Diversity: A Noise Measure for Geometry-Adaptive SGD Schedules
Jun 29, 2026Muhammad Hamza, Ayush GoelStochastic Gradient Descent Hessian
Indian Institute of Technology Kharagpur · Indian Institute of Technology Kharagpur (IIT KGP)

Jun 7, 2026, stat.MLJ/K move · Enter open · S save

Generalization in Nonlinear Least Squares via Learned Feature Geometry

Ayub Kharel, Ilja Kuzborskij, Patrick Rebeschini, Yasin Abbasi-Yadkori

University of Oxford · Google DeepMind · Sapient Intelligence

Generalization Bounds Least Squares Jacobian Neural Tangent Kernel Gradient Descent Nonlinearity+1

Open paper AskPDF arXiv

We study the generalization of ridge-regularized nonlinear least-squares models via on-average algorithmic stability, deriving error bounds for local minimizers in terms of a data-dependent effective dimension that reflects the geometry of the gradient model at the trained parameters, through the empirical Jacobian Gram matrix and a residual-curvature term. In the linear case, where the curvature term vanishes, this recovers the classical effective dimension of the Jacobian kernel covariance, but evaluated at the trained model rather than at initialization as is typical in neural tangent kernel analyses. We further bound this effective dimension via covering complexity of the gradient features, leading to guarantees that depend on learned geometry rather than parameter count. In particular, for manifold-supported data and piecewise Lipschitz Jacobians, the bounds scale with intrinsic dimension, while for one-hidden-layer ReLU networks, the mechanism can be made explicit through counts of activation-stable regions. Experiments on synthetic manifolds, clustered distributions, and benchmark datasets illustrate trained-Jacobian compression, the tightness of the residual-curvature linearization, and agreement between the stability bound and observed generalization gaps. A key feature of our bounds is the simplicity of their derivation, which follows from first principles using the Brascamp-Lieb inequality under strongly log-concave noise.

Abstract

Explore similar work

Generalization in Nonlinear Least Squares via Learned Feature Geometry

Error whitening: Why Gauss-Newton outperforms Newton

Curvature-Weighted Gradient Diversity: A Noise Measure for Geometry-Adaptive SGD Schedules