mlsanityData to 7 Oct 2026

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

arXiv 1612.00547 ↗First posted 2 Dec 2016math.OC cs.DScited by 18

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 6; 2024: 2; 2025: 1; 2026: 3.

18 papers.

Sort:

By area:

  1. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  2. 2023A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guaranteescited by 6
  3. 2023First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessianscited by 6
  4. 2021A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimizationcited by 5
  5. 2022Perseus: A Simple and Optimal High-Order Method for Variational Inequalitiescited by 5
  6. 2024On Newton's Method to Unlearn Neural Networkscited by 5
  7. 2024Cubic regularized subspace Newton for non-convex optimizationcited by 3
  8. 2022A Momentum Accelerated Adaptive Cubic Regularization Method for Nonconvex Optimizationcited by 2
  9. 2023A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimizationcited by 2
  10. 2022Approximate Secular Equations for the Cubic Regularization Subproblemcited by 1
  11. 2023Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networkscited by 1
  12. 2026Data Reconstruction: Identifiability and Optimization with Sample Splittingcited by 1
6 more
  1. 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learningcited by 1
  2. 2026Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrencecited by 1
  3. 2022Cubic-Regularized Newton for Spectral Constrained Matrix Optimization and its Application to Fairnesscited by 0
  4. 2023Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessiancited by 0
  5. 2023Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimizationcited by 0
  6. 2025A Variance-Reduced Cubic-Regularized Newton for Policy Optimizationcited by 0