Catalyst Acceleration for Gradient-Based Non-Convex Optimization

Abstract

We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them on weakly convex objectives, which covers a large class of non-convex functions typically appearing in machine learning and signal processing. In general, the scheme is guaranteed to produce a stationary point with a worst-case efficiency typical of first-order methods, and when the objective turns out to be convex, it automatically accelerates in the sense of Nesterov and achieves near-optimal convergence rate in function values. These properties are achieved without assuming any knowledge about the convexity of the objective, by automatically adapting to the unknown weak convexity constant. We conclude the paper by showing promising experimental results obtained by applying our approach to incremental algorithms such as SVRG and SAGA for sparse matrix factorization and for learning neural networks.

References in corpus (3)

• Non-convex Finite-Sum Optimization Via SCSG Methods
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Cited by in corpus (15)

• The proximal point method revisited
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• A Doubly Accelerated Inexact Proximal Point Method for Nonconvex Composite Optimization Problems
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Robust Implicit Backpropagation
• Accelerated Proximal Envelopes: Application to the Coordinate Descent Method