# First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 5 Sep 2023.

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

- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Lower Bounds for Higher-Order Convex Optimization](https://mlsanity.com/paper/1710.10329/) (2017)
- [Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method](https://mlsanity.com/paper/1905.02671/) (2019)
- [First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles](https://mlsanity.com/paper/2205.03667/) (2022)

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

- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Finding Stationary Points by Comparisons](https://mlsanity.com/paper/2606.27082/) (2026)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)
- [A Parameter-Free First-Order Algorithm for Non-Convex Optimization with tildemkern1mu O(ε-5/3) Global Rate](https://mlsanity.com/paper/2605.02127/) (2026)

## Abstract (arXiv)

In this work, we develop first-order (Hessian-free) and zero-order (derivative-free) implementations of the Cubically regularized Newton method for solving general non-convex optimization problems. For that, we employ finite difference approximations of the derivatives. We use a special adaptive search procedure in our algorithms, which simultaneously fits both the regularization constant and the parameters of the finite difference approximations. It makes our schemes free from the need to know the actual Lipschitz constants. Additionally, we equip our algorithms with the lazy Hessian update that reuse a previously computed Hessian approximation matrix for several iterations. Specifically, we prove the global complexity bound of O( n1/2 ε-3/2) function and gradient evaluations for our new Hessian-free method, and a bound of O( n3/2 ε-3/2 ) function evaluations for the derivative-free method, where n is the dimension of the problem and ε is the desired accuracy for the gradient norm. These complexity bounds significantly improve the previously known ones in terms of the joint dependence on n and ε, for the first-order and zeroth-order non-convex optimization.