# A Universal Catalyst for First-Order Optimization

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2015.

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

- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [Efficient Algorithms for Federated Saddle Point Optimization](https://mlsanity.com/paper/2102.06333/) (2021)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [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)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Accelerated Preference Optimization for Large Language Model Alignment](https://mlsanity.com/paper/2410.06293/) (2024)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)

## Abstract (arXiv)

We introduce a generic scheme for accelerating first-order optimization methods in the sense of Nesterov, which builds upon a new analysis of the accelerated proximal point algorithm. Our approach consists of minimizing a convex objective by approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. This strategy applies to a large class of algorithms, including gradient descent, block coordinate descent, 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. In addition to theoretical speed-up, we also show that acceleration is useful in practice, especially for ill-conditioned problems where we measure significant improvements.