Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
Not on the map. Why?
Abstract (arXiv)
Variance reduction techniques like SVRG provide simple and fast algorithms for optimizing a convex finite-sum objective. For nonconvex objectives, these techniques can also find a first-order stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a second-order stationary point (with small gradient and almost PSD hessian). In this paper, we show that Stabilized SVRG (a simple variant of SVRG) can find an ε-second-order stationary point using only widetildeO(n2/3/ε2+n/ε1.5) stochastic gradients. To our best knowledge, this is the first second-order guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding ε-first-order stationary points.
Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 May 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 5; 2022: 4; 2023: 3; 2024: 0; 2025: 2; 2026: 1.
15 papers.
Sort:
- 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
- 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
- 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
- 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
- 2025Unbiased Gradient Low-Rank Projectioncited by 6
- 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
- 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
- 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
- 2022Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learningcited by 2
- 2021Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learningcited by 1
- 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensingcited by 1
3 more
- 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learningcited by 1
- 2022SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimizationcited by 0
- 2022Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learningcited by 0
- 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning10 Apr 2026
- 2025Unbiased Gradient Low-Rank Projection20 Oct 2025
- 2025Second-Order Convergence in Private Stochastic Non-Convex Optimization21 May 2025
- 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression29 Oct 2023
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time24 May 2023
- 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing20 Mar 2023
- 2022Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning1 Sep 2022
- 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization22 Aug 2022
- 2022SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization17 Jul 2022
- 2022Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning12 Feb 2022
- 2021Escape saddle points by a simple gradient-descent based algorithm28 Nov 2021
- 2021Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning25 Nov 2021
3 more
- 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning10 Aug 2021
- 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method21 Mar 2021
- 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation2 Mar 2021
- 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
- 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
- 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
- 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
- 2025Unbiased Gradient Low-Rank Projectioncited by 6
- 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
- 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
- 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
- 2022Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learningcited by 2
- 2021Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learningcited by 1
- 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensingcited by 1
12 most cited of 15 All 15 (JSON)
- 2026AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning10 Apr 2026
- 2025Unbiased Gradient Low-Rank Projection20 Oct 2025
- 2025Second-Order Convergence in Private Stochastic Non-Convex Optimization21 May 2025
- 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression29 Oct 2023
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time24 May 2023
- 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing20 Mar 2023
- 2022Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning1 Sep 2022
- 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization22 Aug 2022
- 2022SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization17 Jul 2022
- 2022Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning12 Feb 2022
- 2021Escape saddle points by a simple gradient-descent based algorithm28 Nov 2021
- 2021Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning25 Nov 2021
12 newest of 15 All 15 (JSON)