HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 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 support for non-strongly convex objectives. We conclude with extensive experiments showing that acceleration is useful in practice, especially for ill-conditioned problems.
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-01664934
Contributor : Julien Mairal Connect in order to contact the contributor
Submitted on : Tuesday, June 19, 2018 - 9:10:25 AM
Last modification on : Friday, February 4, 2022 - 3:21:15 AM

File

17-748.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01664934, version 2

Collections

Citation

Hongzhou Lin, Julien Mairal, Zaid Harchaoui. Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice. Journal of Machine Learning Research, Microtome Publishing, 2018, 18 (1), pp.7854-7907. ⟨hal-01664934v2⟩

Share

Metrics

Record views

560

Files downloads

185