Fast Incremental Method for Nonconvex Optimization
Not on the map. Why?
Abstract (arXiv)
We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form minx sumi fi(x). Specifically, we analyze the SAGA algorithm within an Incremental First-order Oracle framework, and show that it converges to a stationary point provably faster than both gradient descent and stochastic gradient descent. We also discuss a Polyak's special class of nonconvex problems for which SAGA converges at a linear rate to the global optimum. Finally, we analyze the practically valuable regularized and minibatch variants of SAGA. To our knowledge, this paper presents the first analysis of fast convergence for an incremental aggregated gradient method for nonconvex problems.
Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Mar 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 3; 2022: 2; 2023: 3; 2024: 0; 2025: 1.
9 papers.
- 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
- 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
- 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 62
- 2023Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraintscited by 18
- 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
- 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 10
- 2023Debiasing Conditional Stochastic Optimizationcited by 6
- 2025Non-Convex Federated Optimization under Cost-Aware Client Selectioncited by 1
- 2021Stochastic Learning Approach to Binary Optimization for Optimal Design of Experimentscited by 0
- 2025Non-Convex Federated Optimization under Cost-Aware Client Selection5 Dec 2025
- 2023Debiasing Conditional Stochastic Optimization20 Apr 2023
- 2023Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints29 Mar 2023
- 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization17 Feb 2023
- 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning28 Jul 2022
- 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithms31 Jan 2022
- 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning16 Aug 2021
- 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method17 Feb 2021
- 2021Stochastic Learning Approach to Binary Optimization for Optimal Design of Experiments15 Jan 2021