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).
- Noisy Environments: Shuyao Li and Stephen Wright have shown that randomized second-order algorithms can navigate directions of negative curvature even when gradients and Hessians are noisy, matching the theoretical efficiency of algorithms that have access to perfect information.
- Min-Max Stability: In Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee, Tianyi Lin and Michael Jordan demonstrate that second-order methods can solve saddle-point problems with optimal rates even when using sub-sampled Hessians.
- Efficiency vs. First-Order: Perhaps most surprisingly, Chaobing Song and Ji Liu argue in Inexact Proximal Cubic Regularized Newton Methods for Convex Optimization that by carefully managing error tolerances, these second-order methods can become computationally competitive with—and sometimes superior to—standard Stochastic Gradient Descent (SGD) for large-scale data.
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.