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

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