mlsanityData to 7 Oct 2026

SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points

arXiv 1904.09265 ↗First posted 19 Apr 2019cs.LG cs.DS math.OCcited by 25

Not on the map. Why?

Abstract (arXiv)

We analyze stochastic gradient algorithms for optimizing nonconvex problems. In particular, our goal is to find local minima (second-order stationary points) instead of just finding first-order stationary points which may be some bad unstable saddle points. We show that a simple perturbed version of stochastic recursive gradient descent algorithm (called SSRGD) can find an (ε,δ)-second-order stationary point with widetildeO(√n/ε2 + √n/δ4 + n/δ3) stochastic gradient complexity for nonconvex finite-sum problems. As a by-product, SSRGD finds an ε-first-order stationary point with O(n+√n/ε2) stochastic gradients. These results are almost optimal since Fang et al. [2018] provided a lower bound Omega(√n/ε2) for finding even just an ε-first-order stationary point. We emphasize that SSRGD algorithm for finding second-order stationary points is as simple as for finding first-order stationary points just by adding a uniform perturbation sometimes, while all other algorithms for finding second-order stationary points with similar gradient complexity need to combine with a negative-curvature search subroutine (e.g., Neon2 [Allen-Zhu and Li, 2018]). Moreover, the simple SSRGD algorithm gets a simpler analysis. Besides, we also extend our results from nonconvex finite-sum problems to nonconvex online (expectation) problems, and prove the corresponding convergence results.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

25 papers.

Sort:

  1. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  2. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  3. 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
  4. 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
  5. 2021DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimizationcited by 16
  6. 2022Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimizationcited by 16
  7. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
  8. 2021Faster Rates for Compressed Federated Learning with Client-Variance Reductioncited by 14
  9. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  10. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  11. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  12. 2021Stochastic Gradient Langevin Dynamics with Variance Reductioncited by 7
13 more
  1. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  2. 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
  3. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  4. 2022Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learningcited by 2
  5. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  6. 2024Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problemscited by 2
  7. 2021Faster Perturbed Stochastic Gradient Methods for Finding Local Minimacited by 1
  8. 2025Hessian-guided Perturbed Wasserstein Gradient Flows for Escaping Saddle Pointscited by 1
  9. 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learningcited by 1
  10. 2022Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learningcited by 0
  11. 2024Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimizationcited by 0
  12. 2026Beyond What to Select: A Plug-and-play Oscillatory Data-Volume Scheduling for Efficient Model Trainingcited by 0
  13. 2026Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimizationcited by 0