Fast Incremental Method for Nonconvex Optimization

Abstract

We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form ${\min }_x{\sum }_i{f}_i(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.

References in corpus (3)

• SDCA without Duality
• A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach

Cited by in corpus (16)

• Non-convex Finite-Sum Optimization Via SCSG Methods
• Variance Reduction for Faster Non-Convex Optimization
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Stochastic Learning Approach to Binary Optimization for Optimal Design of Experiments
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• Deep Online Convex Optimization with Gated Games
• Adaptive Step Sizes in Variance Reduction via Regularization
• On the Convergence of SARAH and Beyond
• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization
• Variance Reduction with Sparse Gradients