# Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2016.

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

- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization](https://mlsanity.com/paper/2110.07098/) (2021)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [On Newton's Method to Unlearn Neural Networks](https://mlsanity.com/paper/2406.14507/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [A Momentum Accelerated Adaptive Cubic Regularization Method for Nonconvex Optimization](https://mlsanity.com/paper/2210.05987/) (2022)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Approximate Secular Equations for the Cubic Regularization Subproblem](https://mlsanity.com/paper/2209.13268/) (2022)
- [Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks](https://mlsanity.com/paper/2310.14901/) (2023)
- [Data Reconstruction: Identifiability and Optimization with Sample Splitting](https://mlsanity.com/paper/2602.08723/) (2026)
- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)
- [Cubic-Regularized Newton for Spectral Constrained Matrix Optimization and its Application to Fairness](https://mlsanity.com/paper/2209.01229/) (2022)
- [Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessian](https://mlsanity.com/paper/2311.13094/) (2023)
- [Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization](https://mlsanity.com/paper/2312.03218/) (2023)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)

## Abstract (arXiv)

We consider the minimization of non-convex quadratic forms regularized by a cubic term, which exhibit multiple saddle points and poor local minima. Nonetheless, we prove that, under mild assumptions, gradient descent approximates the textitglobal minimum to within varepsilon accuracy in O(varepsilon-1log(1/varepsilon)) steps for large varepsilon and O(log(1/varepsilon)) steps for small varepsilon (compared to a condition number we define), with at most logarithmic dependence on the problem dimension. When we use gradient descent to approximate the cubic-regularized Newton step, our result implies a rate of convergence to second-order stationary points of general smooth non-convex functions.