Complexity Guarantees for Nonconvex Newton-MR Under Inexact Hessian Information
Inexact-Hessian Newton-MR converges under arbitrarily crude Hessians: linear on q=2 PL functions and O(ε_g^-2) in general nonconvex problems.
Key Findings
Methodology
The method replaces H_k with an approximation \bar H_k and solves the Newton-type minimum-residual subproblem using MINRES. It returns a SOL direction when \|\bar H_kr\|<h\|\bar H_ks\|, or an s-LC residual direction when <r,\bar H_kr>≤sd\|r\|². Armijo backtracking is used for SOL, while forward/backward tracking is used for LC.
Key Results
- Under the q-PL inequality \|g(x)\|²≥2m(f-f⋆)^{2/q}, q=2 yields global linear convergence, while 1≤q<2 becomes sublinear near the optimum. Theorem 1 gives roughly O(log(1/ε_f)) iterations for q=2 and O((f_0-f⋆)ε_g^{-2}/C) to reach \|g\|≤ε_g in general nonconvex settings.
- The descent constant is C=2r(1-r)x min{C_s,C_l}, with C_s=s²d²/[4L_g(L_g+e)^4] and C_l=h²/[L_g((L_g+e)²+h²)]. Thus the theorem does not require either the Hessian error e or the MINRES tolerance h to be small.
- The paper states that machine-learning comparisons were conducted, but the supplied excerpt omits dataset names, baseline values, runtimes, and tables. Consequently, no defensible percentage improvement or ranking can be reported.
Significance
The work addresses a central scalability tension in nonconvex second-order optimization: exact Hessians are expensive, whereas existing guarantees often exclude crude approximations. Assuming only a lower-bounded objective and L_g-Lipschitz gradients, it exploits MINRES residual orthogonality and Krylov-space curvature to preserve descent. The framework covers errors arising in subsampled Newton and Newton Sketch methods, and it reports both iteration and operation complexity, the latter counting gradients and Hessian-vector products.
Technical Contribution
The paper contributes a spectral-norm noise model \|H-\bar H\|≤e, a two-mode Newton-MR algorithm based on SOL and s-LC termination, explicit descent lemmas for both directions, q-PL and general nonconvex iteration bounds, and an operation-complexity analysis based on g-relevant eigenvalues. Unlike many inexact-Newton results, it requires neither Hessian Lipschitz continuity, positive-definite approximations, nor gradient membership in the Hessian range.
Novelty
The fundamental novelty is to use MINRES structure rather than treating the inner solver as a black box. Relative to Newton-CG, trust-region, and cubic-regularization analyses, the paper integrates residual geometry directly into nonconvex guarantees. The authors present this as among the first systematic Newton-type analyses giving fast q-PL rates under mild smoothness, arbitrary Hessian approximation, and arbitrary inner accuracy.
Limitations
- The theorem assumes globally Lipschitz gradients and a lower-bounded objective. Its constants scale with (L_g+e)^4, so the worst-case guarantee can become extremely conservative for noisy Hessians.
- The excerpt does not include the experimental section's tables or dataset identities, preventing verification of practical gains, baseline comparisons, and claimed operation-cost advantages.
Future Work
Promising directions include adaptive selection of e, h, and s; high-probability end-to-end bounds for finite-sum subsampling; randomized preconditioning; and analyses with stochastic-gradient noise. Experiments should test deep networks and non-smooth regularization, while theory should move beyond worst-case spectral constants toward average-case or data-dependent guarantees.
AI Executive Summary
Large-scale machine-learning optimization needs curvature information, yet exact Hessians are expensive to store and apply. Existing Newton-CG, trust-region, and cubic-regularization analyses often require accurate or positive-definite curvature models, assumptions that conflict with subsampling and sketching in practice.
Lim and Roosta propose Newton-MR with an inexact Hessian. MINRES solves the approximate Newton subproblem; a SOL direction is accepted when the residual-to-solution test succeeds, while an s-Limited-Curvature residual direction is used when small or negative curvature is detected. Armijo line searches then enforce sufficient decrease without Hessian damping.
With only lower boundedness and L_g-Lipschitz gradients, the method converges for any Hessian error e and inner tolerance h. It needs O(ε_g^-2) iterations for first-order accuracy in general nonconvex problems and is globally linear on q=2 PL functions. The excerpt mentions machine-learning comparisons but supplies no datasets or numerical tables, so practical superiority cannot be quantified here.
Deep Analysis
Background
First-order methods are cheap but can be slow on ill-conditioned landscapes. Second-order methods improve curvature awareness, but explicit Hessians and Hessian-vector products are costly. Subsampled Newton, Newton Sketch, randomized Hessian sketching, and Krylov methods address scalability. Most line-search Newton methods use CG; Newton-MR instead uses MINRES, which is naturally compatible with symmetric indefinite or singular systems.
Core Problem
The objective is a twice continuously differentiable, lower-bounded, nonconvex function. An approximate Hessian may be indefinite or singular, and the gradient need not lie in its range. Standard relative-residual stopping rules may therefore fail. The paper seeks iteration and operation guarantees despite arbitrary Hessian approximation and inexact inner solves.
Innovation
First, it adopts the spectral error model \|H-\bar H\|≤e. Second, MINRES termination distinguishes an acceptable solution direction from a finite-curvature residual direction. Third, separate line-search arguments yield explicit decrease for both cases. Fourth, the analysis covers q-PL functions and general nonconvex objectives. Finally, g-relevant eigenvalues connect the approximate Hessian spectrum to inner operation complexity, without adding Hessian regularization.
Methodology
- �� Input x_k, g_k, \bar H_k, inner tolerance h, and curvature threshold s.
- �� MINRES generates residuals r_k^(t) and iterates s_k^(t).
- �� If \|\bar H_kr\|<h\|\bar H_ks\|, return SOL=s; if <r,\bar H_kr>≤sd\|r\|², return LC=r.
- �� Apply backward Armijo search to SOL and forward/backward search to LC.
- �� Update x_{k+1}=x_k+a_kd_k.
- �� Lipschitz-gradient smoothness yields f_{k+1}-f_k≤-C\|g_k\|².
- �� C=2r(1-r)x min{C_s,C_l}, with the constants stated in Theorem 1.
Experiments
The paper reports comparisons with several alternatives on machine-learning problems and discusses Hessian regularization in the appendix. However, the supplied text ends during the operation-complexity section and contains no experimental tables, dataset names, model specifications, metrics, hyperparameters, or ablations. The grounded experimental claim is therefore limited to the existence of such comparisons; finite-sum and subsampled-Hessian settings are the relevant motivating scenarios.
Results
For q=2 PL functions, the function gap contracts by approximately 1-2mC per iteration. For 1≤q<2, the rate slows near optimality. In general nonconvex optimization, reaching \|g\|≤ε_g requires at most (f_0-f⋆)ε_g^{-2}/C iterations. This O(ε_g^-2) order matches the known second-order scale under only Lipschitz-gradient assumptions. Practical numerical comparisons cannot be quantified from the excerpt.
Applications
The framework suits finite-sum learning problems where approximate Hessian-vector products are available but full Hessians are not. Subsampled Newton can tune e through sample size, while Newton Sketch uses randomized curvature compression. Practitioners should jointly monitor MINRES work, line-search evaluations, spectral conditioning, and gradient cost rather than relying on outer iteration counts alone.
Limitations & Outlook
The guarantees rely on global gradient Lipschitzness, lower boundedness, and a symmetric spectral-norm Hessian error model. Constants can deteriorate sharply with e and depend on s and h. The supplied material lacks the numerical evidence needed to assess real-world speedups, robustness to stochastic gradients, and behavior in deep networks. Future work should develop adaptive, data-dependent, high-probability operation bounds.
Plain Language Accessible to non-experts
Imagine hiking through a foggy mountain range to find the lowest valley. A basic hiker only feels the slope underfoot: each step is cheap, but narrow valleys cause frustratingly slow progress. A second-order hiker wants a map of nearby terrain, yet drawing a complete map is expensive.
Newton-MR allows a rough map. MINRES tries several routes using limited clues. If it finds a reliable route toward the valley, the method follows it; if the terrain suggests a dangerous dip or strange ridge, it switches to a direction that is guaranteed to go downhill. A line search acts like a safety check: if a proposed stride is too long, shorten it until the altitude really decreases.
The theoretical message is striking: even a very inaccurate map and an unfinished route search need not destroy progress. On landscapes with a favorable valley structure, progress is proportional from step to step; on more general terrain, the method eventually finds a nearly flat location. The excerpt mentions machine-learning tests, but gives no numerical table.
ELI14 Explained like you're 14
Pretend you are playing a game where the goal is to reach the lowest point on a huge, foggy map. The simplest strategy checks which neighboring square is lower and moves there. That works, but it can be painfully slow in a long, skinny valley.
Newton-MR is like using a noisy radar. It does not scan the entire map, because that would take forever. MINRES sends out several probes and combines their clues. If the probes suggest a good route, the player follows it. If they detect a weird slope or a pit, the player chooses a direction that should definitely lower the score. A safety check keeps the move from being too large.
What is surprising? The radar can be quite inaccurate, and the probing can stop early, yet the paper still proves that the score keeps improving. On certain friendly maps, improvement happens at a steady rate; on ordinary maps, the player eventually reaches a spot where almost no uphill direction remains. The supplied excerpt does not show the actual test scores.
Glossary
Newton-MR (Newton Minimum Residual)
A second-order optimization framework that seeks a direction by minimizing the residual of a Newton equation. It uses MINRES and can handle symmetric indefinite or singular curvature models.
The paper extends Newton-MR to inexact Hessian information and nonconvex objectives.
MINRES (Minimum Residual)
A Krylov-subspace method that minimizes linear-system residuals over expanding subspaces. Residual orthogonality and monotonicity are central to the descent proof.
It generates both SOL solution directions and LC residual directions.
q-PL condition
The inequality \|g(x)\|²≥2m(f-f⋆)^{2/q}, which links gradient magnitude to objective gap without requiring convexity. q=2 gives the strongest rate considered here.
It yields global linear convergence for q=2 and sublinear local behavior for q<2.
Inexact Hessian
An approximation \bar H satisfying the spectral error bound \|H-\bar H\|≤e. It models subsampling, sketching, and other curvature approximations.
The main theorem allows arbitrary positive e.
s-Limited Curvature direction
A direction r satisfying <r,Ar>≤sd\|r\|², indicating sufficiently small or negative curvature. It provides a descent alternative when a Newton-like iterate is unreliable.
MINRES returns this residual direction when the curvature test triggers.
Operation complexity
The total computational work measured through gradient and Hessian-vector product evaluations, not merely outer iterations. It better reflects large-scale implementations.
The paper analyzes it using g-relevant eigenvalues.
Open Questions Unanswered questions from this research
- 1 How should e, h, and s be selected adaptively so that theoretical constants are not overly pessimistic? The current analysis treats them as prescribed parameters.
- 2 The excerpt lacks numerical tables, leaving performance under deep-network stochastic noise and realistic Hessian-vector costs unresolved.
Applications
Immediate Applications
Subsampled Newton training
For finite-sum objectives, construct \bar H from a sample subset, control e through sample size, and solve with MINRES. This avoids a full Hessian while retaining a principled descent mechanism.
Newton Sketch optimization
Use randomized sketches to compress curvature in large regression or machine-learning models. Early MINRES termination can reduce work, provided practitioners track matrix-vector products and line-search evaluations.
Long-term Vision
Scalable nonconvex second-order systems
Combine the framework with distributed Hessian-vector products, adaptive sampling, and randomized preconditioning. Such systems could bring low-memory curvature methods to very large neural models, although stochastic robustness remains to be demonstrated.
Abstract
We consider an extension of the Newton-MR algorithm for nonconvex unconstrained optimization to the settings where Hessian information is approximated. Under a particular noise model on the Hessian matrix, we investigate the iteration and operation complexities of this variant to achieve appropriate sub-optimality criteria in several nonconvex settings. We do this by first considering functions that satisfy the (generalized) Polyak-Łojasiewicz condition, a special sub-class of nonconvex functions. We show that, under certain conditions, our algorithm achieves global linear convergence rate. We then consider more general nonconvex settings where the rate to obtain first order sub-optimality is shown to be sub-linear. In all these settings, we show that our algorithm converges regardless of the degree of approximation of the Hessian as well as the accuracy of the solution to the sub-problem. Finally, we compare the performance of our algorithm with several alternatives on a few machine learning problems.