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

Hongzhou Lin, Julien Mairal, Zaïd Harchaoui

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.

Introduction

In the world of machine learning, training a model often boils down to solving a massive convex optimization problem. While we have a library of reliable first-order methods—like Stochastic Variance Reduced Gradient (SVRG) or SAGA—not all of them are "accelerated" in the sense of Nesterov. Historically, adding acceleration was an algorithm-specific endeavor requiring complex new proofs for each individual method.

In this paper, Lin et al. introduce Catalyst, a generic framework that acts as a wrapper to accelerate almost any first-order optimization method. By solving a sequence of well-conditioned auxiliary problems, Catalyst brings the benefits of Nesterov’s acceleration to a wide array of algorithms, providing both theoretical optimality and practical speedups.

The Catalyst Framework

Catalyst is built on an inner-outer loop structure based on Moreau-Yosida smoothing (also known as the proximal point algorithm).

  • The Outer Loop: This loop maintains an "accelerated" sequence of iterates using Nesterov’s extrapolation. It essentially asks: "Where should we look next to get the most progress?"
  • The Inner Loop: Instead of solving the original, potentially difficult objective, the inner loop solves a "smoothed" auxiliary problem. This sub-problem is regularized to be strongly convex and well-conditioned, making it much easier for a base algorithm (the "method $\mathcal{M}$") to solve quickly.
  • The "Secret Sauce": The paper’s core contribution lies in its inexactness criteria and warm-start strategies. You don't need to solve the inner sub-problems perfectly. The authors provide specific stopping criteria (how accurate the inner solution needs to be) and show that starting the inner loop using a specific combination of previous iterates (warm-starting) is essential for maintaining global efficiency.

Theoretical Complexity

The primary theoretical contribution is the establishment of near-optimal convergence rates for a wide class of algorithms. Catalyst achieves the best known bounds for first-order methods, matching optimal rates up to a logarithmic factor.

Comparison of convergence rates for various algorithms with and without the Catalyst wrapper.

As shown in the table above, Catalyst provides significant improvements, especially for ill-conditioned problems (where the strong convexity parameter $\mu$ is small) and non-strongly convex objectives ($\mu = 0$). For example, for incremental methods like SVRG or SAGA, the complexity improves from $O((n + \frac{\bar{L}}{\mu}) \log(\frac{1}{\epsilon}))$ to $\tilde{O}((n + \sqrt{\frac{n\bar{L}}{\mu}}) \log(\frac{1}{\epsilon}))$. This square-root dependence on the condition number is the hallmark of Nesterov-style acceleration.

Key Insights and Practical Guidelines

  • Smoothing as a Bridge: By using the Moreau envelope, Catalyst effectively turns a "jagged" or "flat" optimization landscape into a smooth, well-behaved one.
  • The Balancing Act: The smoothing parameter $\kappa$ allows you to balance the work. A large $\kappa$ makes the inner sub-problems very easy to solve but requires more outer-loop iterations. The authors provide a "rule of thumb" to maximize the ratio of inner-to-outer efficiency.
  • The "One-Pass" Heuristic: One of the most surprising practical findings is that for incremental methods, simply performing one pass over the data in the inner loop (the "one-pass strategy") often satisfies the theoretical requirements for acceleration and performs best in practice.
  • Stability via Regularization: Methods like MISO, which can be numerically unstable on ill-conditioned problems, become robust when wrapped in Catalyst because they are only ever asked to solve well-conditioned sub-problems.

Experimental Evaluation

The authors evaluated Catalyst across six diverse machine learning datasets, focusing on large-scale classification tasks such as covtype, alpha, real-sim, and rcv1, as well as computer vision features from MNIST-CKN and CIFAR-CKN. They tested these against common formulations including $\ell_2$-regularized Logistic Regression, LASSO, and Elastic-Net.

Key results from these experiments include:

  • Empirical Speedups: On ill-conditioned problems, Catalyst-SVRG and Catalyst-SAGA reached high accuracy significantly faster than their non-accelerated versions.
  • Universal Support: The framework successfully provided a path to use SVRG and MISO on non-strongly convex LASSO problems, where they previously lacked direct support.
  • Generalization: The acceleration on training loss translates well to test error, meaning the speedup doesn't come at the cost of the model's ability to generalize to new data.

Conclusion

For engineers and researchers, Catalyst offers a rare "free lunch": a way to take the optimization code you already have and make it faster and more stable with a relatively simple wrapper. While it carries a small logarithmic complexity penalty compared to algorithms specifically designed from the ground up to be accelerated (like Katyusha), its universality makes it a powerful tool for modern large-scale machine learning.

Summary updated

Abstract

We introduce a generic scheme for accelerating gradient-based optimization\nmethods in the sense of Nesterov. The approach, called Catalyst, builds upon\nthe inexact accelerated proximal point algorithm for minimizing a convex\nobjective function, and consists of approximately solving a sequence of\nwell-chosen auxiliary problems, leading to faster convergence. One of the keys\nto achieve acceleration in theory and in practice is to solve these\nsub-problems with appropriate accuracy by using the right stopping criterion\nand the right warm-start strategy. We give practical guidelines to use Catalyst\nand present a comprehensive analysis of its global complexity. We show that\nCatalyst applies to a large class of algorithms, including gradient descent,\nblock coordinate descent, incremental algorithms such as SAG, SAGA, SDCA, SVRG,\nMISO/Finito, and their proximal variants. For all of these methods, we\nestablish faster rates using the Catalyst acceleration, for strongly convex and\nnon-strongly convex objectives. We conclude with extensive experiments showing\nthat acceleration is useful in practice, especially for ill-conditioned\nproblems.\n
BibTeX
@article{lin2017catalyst,
  author = {Hongzhou Lin and Julien Mairal and Zaïd Harchaoui},
  title = {{Catalyst Acceleration for First-order Convex Optimization: from Theory\textbackslash\{\}n to Practice}},
  journal = {J. Mach. Learn. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=35X5fzw5G4S},
}
Figure