# Second-order optimization with lazy Hessians

arXiv: https://arxiv.org/abs/2212.00781 · HTML: https://mlsanity.com/paper/2212.00781/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 1 Dec 2022.

## Builds on (most cited first, 13 of 13)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Gradient Regularization of Newton Method with Bregman Distances](https://mlsanity.com/paper/2112.02952/) (2021)
- [New Results on Superlinear Convergence of Classical Quasi-Newton Methods](https://mlsanity.com/paper/2004.14866/) (2020)
- [Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method](https://mlsanity.com/paper/1905.02671/) (2019)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Convex optimization based on global lower second-order models](https://mlsanity.com/paper/2006.08518/) (2020)
- [New Proximal Newton-Type Methods for Convex Optimization](https://mlsanity.com/paper/2007.09525/) (2020)
- [Affine-invariant contracting-point methods for Convex Optimization](https://mlsanity.com/paper/2009.08894/) (2020)

## Built on by (most cited first, 15 of 15)

- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [HIP: Hessian Interatomic Potentials without derivatives](https://mlsanity.com/paper/2509.21624/) (2025)
- [Exact Gauss-Newton Optimization for Training Deep Neural Networks](https://mlsanity.com/paper/2405.14402/) (2024)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [SASSHA: Sharpness-aware Adaptive Second-order Optimization with Stable Hessian Approximation](https://mlsanity.com/paper/2502.18153/) (2025)
- [Gradient Regularized Natural Gradients](https://mlsanity.com/paper/2601.18420/) (2026)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)
- [Incremental Gauss--Newton Methods with Superlinear Convergence Rates](https://mlsanity.com/paper/2407.03195/) (2024)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)
- [Second-Order Optimization with Asynchronous Curvature](https://mlsanity.com/paper/2510.15714/) (2025)
- [Near-Optimal Convex Optimization with Lazy Second-Order Oracles](https://mlsanity.com/paper/2610.03222/) (2026)
- [Randomized Momentum Transport with Cheap Predictors](https://mlsanity.com/paper/2610.13789/) (2026)

## Abstract (arXiv)

We analyze Newton's method with lazy Hessian updates for solving general possibly non-convex optimization problems. We propose to reuse a previously seen Hessian for several iterations while computing new gradients at each step of the method. This significantly reduces the overall arithmetical complexity of second-order optimization schemes. By using the cubic regularization technique, we establish fast global convergence of our method to a second-order stationary point, while the Hessian does not need to be updated each iteration. For convex problems, we justify global and local superlinear rates for lazy Newton steps with quadratic regularization, which is easier to compute. The optimal frequency for updating the Hessian is once every d iterations, where d is the dimension of the problem. This provably improves the total arithmetical complexity of second-order algorithms by a factor √d.