mlsanityData to 7 Oct 2026

Stochastic Cubic Regularization for Fast Nonconvex Optimization

arXiv 1711.02838 ↗First posted 8 Nov 2017cs.LG math.OC stat.MLcited by 55

Not on the map. Why?

Abstract (arXiv)

This paper proposes a stochastic variant of a classic algorithm---the cubic-regularized Newton method [Nesterov and Polyak 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only mathcaltildeO(ε-3.5) stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the mathcaltildeO(ε-4) rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.

Key facts. Cited by 55 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 9; 2023: 13; 2024: 10; 2025: 4; 2026: 6.

55 papers.

Sort:

By area:

  1. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  2. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  3. 2021An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangianscited by 25
  4. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  5. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 18
  6. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  7. 2021Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programmingcited by 16
  8. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  9. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  10. 2021Better SGD using Second-order Momentumcited by 14
  11. 2022SP2: A Second Order Stochastic Polyak Methodcited by 13
  12. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
38 more
  1. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  2. 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 10
  3. 2022Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batchescited by 9
  4. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  5. 2021Direct-Search for a Class of Stochastic Min-Max Problemscited by 7
  6. 2022Adaptive Learning Rates for Faster Stochastic Gradient Methodscited by 7
  7. 2023A Cubic-regularized Policy Newton Algorithm for Reinforcement Learningcited by 7
  8. 2024Improving Stochastic Cubic Newton with Momentumcited by 6
  9. 2021A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimizationcited by 5
  10. 2024On Newton's Method to Unlearn Neural Networkscited by 5
  11. 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitzcited by 4
  12. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 4
  13. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  14. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  15. 2024Cubic regularized subspace Newton for non-convex optimizationcited by 3
  16. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  17. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  18. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  19. 2023Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Functioncited by 2
  20. 2024Two trust region type algorithms for solving nonconvex-strongly concave minimax problemscited by 2
  21. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  22. 2021Escaping Saddle Points with Compressed SGDcited by 1
  23. 2022A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimizationcited by 1
  24. 2022Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretationcited by 1
  25. 2022Approximate Secular Equations for the Cubic Regularization Subproblemcited by 1
  26. 2023Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networkscited by 1
  27. 2023A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guaranteescited by 1
  28. 2023Efficiently Escaping Saddle Points for Policy Optimizationcited by 1
  29. 2024Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentumcited by 1
  30. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGDcited by 1
  31. 2026Stochastic Control Methods for Optimizationcited by 1
  32. 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learningcited by 1
  33. 2026Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrencecited by 1
  34. 2021Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methodscited by 0
  35. 2021Non-PSD Matrix Sketching with Applications to Regression and Optimizationcited by 0
  36. 2022HOUDINI: Escaping from Moderately Constrained Saddlescited by 0
  37. 2023Stochastic Dimension-reduced Second-order Methods for Policy Optimizationcited by 0
  38. 2023Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularizationcited by 0

50 most cited of 55 All 55 (JSON)