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

Hongzhou Lin, Julien Mairal, Zaïd Harchaoui

TL;DR

This paper introduces "Catalyst," a generic framework for accelerating first-order optimization methods, particularly for large-scale machine learning problems. Catalyst achieves faster convergence by approximately solving a sequence of well-conditioned auxiliary problems, offering significant speedups for various algorithms, including incremental methods, and even extending their applicability to non-strongly convex objectives.

What Problem Does This Paper Address?

Many machine learning and signal processing problems are formulated as minimizing a convex objective function, often a large sum of simpler functions (e.g., empirical risk minimization). While efficient first-order optimization methods exist, their convergence rates can be suboptimal, especially for ill-conditioned problems. Nesterov's acceleration technique has been successful for smooth and strongly convex functions, but its application to a broader class of algorithms, particularly incremental methods and non-strongly convex objectives, remained an open question. This paper aims to provide a unified framework to accelerate these methods, offering improved convergence rates and practical benefits.

Methods

The core of Catalyst is an "inner-outer loop" structure. The outer loop uses Nesterov's extrapolation technique to accelerate convergence. The inner loop involves approximately solving a sequence of strongly convex auxiliary problems. These auxiliary problems are constructed using a "smoothing" technique, specifically the Moreau envelope, which transforms the original (potentially ill-conditioned or non-strongly convex) objective into a well-conditioned, smooth, and strongly convex one.

Key methodological contributions include:

  • Generic Acceleration: Catalyst acts as a wrapper, taking any optimization method M that has linear convergence for strongly convex problems and producing an accelerated version A.
  • Inexact Proximal Point Algorithm: The inner loop solves approximate proximal point problems. The paper provides practical guidelines for choosing appropriate stopping criteria (absolute and relative accuracy) and warm-start strategies to ensure efficient and accurate subproblem solutions.
  • Support for Non-Strongly Convex Objectives: Unlike many existing acceleration techniques that require strong convexity, Catalyst directly handles general convex objectives without needing to add artificial regularization.
  • Moreau Envelope: The use of the Moreau envelope (or its approximate variant) is central to creating well-conditioned subproblems.

Datasets

The paper evaluates Catalyst on six machine learning datasets:

  • covtype
  • alpha
  • real-sim
  • rcv1
  • MNIST-CKN
  • CIFAR-CKN

These datasets vary in size and dimension and are used with three common optimization formulations: logistic regression, L1-regularized linear regression (LASSO), and L1-L2 regularized linear regression (Elastic-Net).

Key Insights and Ideas

  • Universality of Acceleration: Catalyst demonstrates that acceleration is not limited to specific algorithms but can be achieved generically for a broad class of first-order methods, provided they have linear convergence on strongly convex problems.
  • The Power of Well-Conditioned Subproblems: By transforming the original problem into a sequence of well-conditioned auxiliary problems via smoothing, Catalyst effectively bypasses the ill-conditioning issues that plague many optimization algorithms.
  • Practical Acceleration for Incremental Methods: The paper shows that incremental methods like SAG, SAGA, SDCA, and SVRG, which are crucial for large-scale problems, can be significantly accelerated by Catalyst, often achieving near-optimal convergence rates.
  • Bridging the Gap for Non-Strongly Convex Problems: Catalyst's ability to accelerate methods on non-strongly convex objectives without explicit regularization is a significant theoretical and practical advantage.
  • Warm-Starts are Crucial: The choice of warm-start strategy for the inner loop is identified as critical for achieving practical speedups and good performance.

Key Results

  • Theoretical Speedups: Catalyst provides provably faster convergence rates for various algorithms, including gradient descent, SAG, SAGA, SDCA, SVRG, and MISO/Finito, for both strongly convex and non-strongly convex objectives. The rates are often optimal up to logarithmic factors.
  • Empirical Validation: Extensive experiments show that Catalyst consistently accelerates the tested algorithms, especially for ill-conditioned problems. The "one-pass" strategy for incremental methods (a heuristic aggressive warm-start) proved particularly effective in practice.
  • Improved Numerical Stability: For some methods like MISO, Catalyst not only accelerates but also improves numerical stability in ill-conditioned regimes.
  • Generalization Error: Experiments suggest that acceleration on the training data does not negatively impact generalization error on unseen test data.

Limitations and Future Work

  • Theoretical vs. Practical Parameter Choice: While the paper provides theoretical guidelines for choosing the smoothing parameter $\kappa$, experimental results suggest that Catalyst can be robust to values slightly different from the theoretical optimum. Future work could explore more adaptive strategies for $\kappa$.
  • Versatility Beyond Finite Sums: The paper focuses on finite-sum optimization problems. The authors suggest that Catalyst's core ideas could be applied to other optimization settings, potentially leading to new accelerated algorithms.
  • Non-convex Optimization: The current framework is for convex optimization. Extending Catalyst to non-convex settings is a natural direction for future research.

Summary updated

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.
BibTeX
@article{lin2017catalyst,
  author = {Hongzhou Lin and Julien Mairal and Zaïd Harchaoui},
  title = {{Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice}},
  journal = {J. Mach. Learn. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=35X5fzw5G4S},
}
Figure