mlsanityData to 14 Oct 2026

Faster Perturbed Stochastic Gradient Methods for Finding Local Minima

arXiv 2110.13144 ↗First posted 25 Oct 2021math.OC cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Escaping from saddle points and finding local minimum is a central problem in nonconvex optimization. Perturbed gradient methods are perhaps the simplest approach for this problem. However, to find (ε, √ε)-approximate local minima, the existing best stochastic gradient complexity for this type of algorithms is tilde O(ε-3.5), which is not optimal. In this paper, we propose LENA (Last stEp shriNkAge), a faster perturbed stochastic gradient framework for finding local minima. We show that LENA with stochastic gradient estimators such as SARAH/SPIDER and STORM can find (ε, εH)-approximate local minima within tilde O(ε-3 + εH-6) stochastic gradient evaluations (or tilde O(ε-3) when εH = √ε). The core idea of our framework is a step-size shrinkage scheme to control the average movement of the iterates, which leads to faster convergence to the local minima.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 26 of its 35 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

26 of 35 references.

References · 26

  1. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  4. 2017How to Escape Saddle Points Efficientlycited by 285
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  6. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  7. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  8. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  9. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  10. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  11. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  12. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
14 more
  1. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  2. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  3. 2018Escaping Saddles with Stochastic Gradientscited by 66
  4. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  5. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  6. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  7. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  8. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  9. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  10. 2019Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimizationcited by 32
  11. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  12. 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
  13. 2016Accelerated Methods for Non-Convex Optimizationcited by 20
  14. 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learningcited by 1