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

arXiv: https://arxiv.org/abs/1712.05654 · HTML: https://mlsanity.com/paper/1712.05654/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2017.

## Built on by (most cited first, 30 of 39)

- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition](https://mlsanity.com/paper/2104.06718/) (2021)
- [Anticorrelated Noise Injection for Improved Generalization](https://mlsanity.com/paper/2202.02831/) (2022)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Electrical Load Forecasting in Smart Grid: A Personalized Federated Learning Approach](https://mlsanity.com/paper/2411.10619/) (2024)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [DIPPA: An improved Method for Bilinear Saddle Point Problems](https://mlsanity.com/paper/2103.08270/) (2021)
- [Accelerated Preference Optimization for Large Language Model Alignment](https://mlsanity.com/paper/2410.06293/) (2024)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration](https://mlsanity.com/paper/2410.07272/) (2024)
- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)
- [Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization](https://mlsanity.com/paper/2106.08855/) (2021)
- [On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regression](https://mlsanity.com/paper/2204.07702/) (2022)
- [Statistical and Computational Guarantees for Influence Diagnostics](https://mlsanity.com/paper/2212.04014/) (2022)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)

## Abstract (arXiv)

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.