Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems
Not on the map. Why?
Abstract (arXiv)
This paper develops a new dimension-free Azuma-Hoeffding type bound on summation norm of a martingale difference sequence with random individual bounds. With this novel result, we provide high-probability bounds for the gradient norm estimator in the proposed algorithm Prob-SARAH, which is a modified version of the StochAstic Recursive grAdient algoritHm (SARAH), a state-of-art variance reduced algorithm that achieves optimal computational complexity in expectation for the finite sum problem. The in-probability complexity by Prob-SARAH matches the best in-expectation result up to logarithmic factors. Empirical experiments demonstrate the superior probabilistic performance of Prob-SARAH on real datasets compared to other popular algorithms.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 20 of its 33 references that are in the map. First posted on arXiv 29 Jan 2024.
Builds on
20 of 33 references.
References · 20
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
- 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
- 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
- 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
- 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
- 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
- 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
- 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
- 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
- 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
8 more
- 2018A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimizationcited by 33
- 2019Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimizationcited by 31
- 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
- 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 25
- 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
- 2016Less than a Single Pass: Stochastically Controlled Stochastic Gradient Methodcited by 17
- 2020Adaptivity of Stochastic Gradient Methods for Nonconvex Optimizationcited by 16
- 2019On the Adaptivity of Stochastic Gradient-Based Optimizationcited by 7
Built on by
Citing papers per year: 2025: 2.
2 papers.