# Faster Perturbed Stochastic Gradient Methods for Finding Local Minima

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

## Key facts

- Cited by 1 papers 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 (most cited first, 26 of 26)

- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Stochastic Recursive Gradient Algorithm for Nonconvex Optimization](https://mlsanity.com/paper/1705.07261/) (2017)

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

- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)

## 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.