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

By Hongzhou Lin, Julien Mairal, Zaïd Harchaoui. 2017

153 citations recorded by the source corpus.

We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact acceler- ated 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 key 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. In this paper, we give practical guidelines to use Catalyst and present a comprehensive theoretical 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, Finito/MISO, and their proximal variants. For all of these methods, we provide acceleration and explicit sup- port for non-strongly convex objectives. We conclude with extensive experiments showing that acceleration is useful in practice, especially for ill-conditioned problems.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Personalized Federated Learning with Moreau Envelopes (2020, methodology): “Finally, we review several useful properties of the Moreau envelope such as smoothing and preserving convexity as follows (see the review and proof for the convex case in [40, 46, 47] and for nonconvex smooth case in [48], respectively): Proposition 1.”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, background): “It also seems possible to combine our analysis with acceleration in order to improve the sample complexity to T = O( 1 √ ε ); the Catalyst of [14] and [20] is a possible recipe for such acceleration.”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “Finally, variance reduced methods can also be accelerated, as has been shown for the loop based methods such as Katyusha [3] or using the Universal catalyst [17].”
Understanding the acceleration phenomenon via high-resolution differential equations (2018, background): “See also [18,19,21,23,32,37] for a number of other recent contributions to the study of the acceleration phenomenon.”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “One may also use the Catalyst framework [24, 34] and proximal point iteration [10, 28] to further accelerate when the problem is ill-conditioned.”
Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon more (2019, methodology): “• catalyst-miso: its accelerated variant, by using the Catalyst approach of Lin et al. [2018];”