Robust Convergence of Inexact Second-Order Optimization

This direction is merged into another direction: saddle point stagnation. Its last version stays readable and citable here.

Version 1 of 120 papers25 conceptsfrozen 2026-10-04

In the hierarchy of optimization, second-order methods like Newton’s method are the gold standard for speed. By using the Hessian—the matrix of second derivatives—these algorithms "see" the curvature of the loss landscape, allowing them to take aggressive, direct paths to the optimum.

However, in large-scale machine learning, the gold standard is often too expensive to mine. Calculating an exact Hessian for a model with millions of parameters is computationally prohibitive, and solving the resulting linear systems can be even worse. This has led to a surge in research into inexact second-order methods: algorithms that use "good enough" approximations of curvature to maintain the lightning-fast convergence of Newton-type methods at a fraction of the cost.

The Intuition of Robustness

The central insight of this research direction is that second-order methods are surprisingly forgiving. You do not need the exact Hessian to reap the benefits of second-order optimization.

As Sai Praneeth Karimireddy, Martin Jaggi, and Sebastian U. Stich demonstrate in Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients, the global linear convergence of Newton-type methods is robust to both Hessian approximations and inexact subproblem solutions. This means practitioners can use "sketched" Hessians (compressed versions of the matrix) or matrix-free products without losing the fundamental speedup that second-order information provides.

Safety Through Cubic Regularization

When we move from convex to non-convex landscapes—the kind found in deep learning—standard Newton methods can become unstable, often getting "tricked" by saddle points. To fix this, researchers use Adaptive Cubic Regularization (ARC). Instead of just fitting a quadratic bowl to the local landscape, ARC adds a cubic term that penalizes steps that go too far into unknown territory.

The power of ARC is that it remains theoretically optimal even when every component is an approximation. Zhewei Yao and Farbod Roosta-Khorasani show in Inexact Non-Convex Newton-Type Methods that as long as the approximation errors in the gradient and Hessian are bounded relative to the target accuracy, the algorithm maintains its worst-case iteration complexity. This "error budget" allows for significant computational shortcuts, such as using sub-sampled Hessians or inexact solvers like Krylov subspace methods, as explored by Michael Ng and Yihang Gao in A Momentum Accelerated Adaptive Cubic Regularization Method for Nonconvex Optimization.

Acceleration Without Magic Numbers

One of the biggest hurdles in optimization is tuning "magic numbers"—hyperparameters like the Lipschitz constant. Traditional accelerated methods (like Nesterov’s) require knowing these constants upfront.

Recent work by Bo Jiang 0007 and Shuzhong Zhang has developed A Unified Scheme to Accelerate Adaptive Cubic Regularization and Gradient Methods for Convex Optimization. Their framework is fully adaptive, meaning it "feels out" the local curvature and adjusts its step size and regularization on the fly. Crucially, they prove that this acceleration holds even when the Hessian is approximated via finite differences of gradients, bridging the gap between high-level theory and practical engineering.

Scaling to High Dimensions and Min-Max Problems

The robustness of these methods extends to the most challenging frontiers of modern AI: high-dimensional non-convex optimization and min-max problems (like those used to train GANs).

Why It Works: The Gradient-Normalized Perspective

The underlying reason for this success is being codified into new theoretical frameworks. Andrei Semenov, Martin Jaggi, and Nikita Doikov propose a concept called Gradient-Normalized Smoothness (GNS) in Gradient-Normalized Smoothness for Optimization with Approximate Hessians. GNS provides a formal justification for why cheap approximations—like the Fisher matrix—are often just as effective as the exact Hessian. It suggests that as long as the approximation captures the "dominant" directions of the curvature, the optimizer will still move toward the goal with second-order efficiency.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_robust_convergence_of_inexact_second_ord_31d8c92b,
  title = {Robust Convergence of Inexact Second-Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-convergence-of-inexact-second-order-optimization/rdr_31d8c92bedbf4d69b61030aaf6bac119},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_robust_convergence_of_inexact_second_ord_31d8c92b_v1,
  title = {Robust Convergence of Inexact Second-Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-convergence-of-inexact-second-order-optimization/rdr_31d8c92bedbf4d69b61030aaf6bac119/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}