Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice

Abstract

We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact accelerated proximal point algorithm for minimizing a convex objective function, and consists of approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. One of the keys to achieve acceleration in theory and in practice is to solve these sub-problems with appropriate accuracy by using the right stopping criterion and the right warm-start strategy. We give practical guidelines to use Catalyst and present a comprehensive analysis of its global complexity. We show that Catalyst applies to a large class of algorithms, including gradient descent, block coordinate descent, incremental algorithms such as SAG, SAGA, SDCA, SVRG, MISO/Finito, and their proximal variants. For all of these methods, we establish faster rates using the Catalyst acceleration, for strongly convex and non-strongly convex objectives. We conclude with extensive experiments showing that acceleration is useful in practice, especially for ill-conditioned problems.

link to publisher website: http://jmlr.org/papers/volume18/17-748/17-748.pdf

References in corpus (9)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Proximal Stochastic Dual Coordinate Ascent
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Tight Complexity Bounds for Optimizing Composite Objectives
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• Envelope Functions: Unifications and Further Properties

Cited by in corpus (5)

• Personalized Federated Learning with Moreau Envelopes
• The importance of better models in stochastic optimization
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Accelerated meta-algorithm for convex optimization
• Robust Implicit Backpropagation