mlsanityData to 7 Oct 2026

A Universal Catalyst for First-Order Optimization

arXiv 1506.02186 ↗First posted 6 Jun 2015math.OCcited by 54

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 13; 2023: 8; 2024: 10; 2025: 6; 2026: 3.

54 papers.

Sort:

By area:

  1. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  2. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  3. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  4. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  5. 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
  6. 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
  7. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  8. 2022Faster federated optimization under second-order similaritycited by 18
  9. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  10. 2021Acceleration in Distributed Optimization under Similaritycited by 17
  11. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  12. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
38 more
  1. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  2. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  3. 2022Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batchescited by 9
  4. 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
  5. 2022DADAO: Decoupled Accelerated Decentralized Asynchronous Optimizationcited by 8
  6. 2021Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentumcited by 7
  7. 2023A Coefficient Makes SVRG Effectivecited by 7
  8. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  9. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 6
  10. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  11. 2024Accelerated Preference Optimization for Large Language Model Alignmentcited by 5
  12. 2021First-Order Methods for Convex Optimizationcited by 4
  13. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  14. 2022Adaptive Accelerated (Extra-)Gradient Methods with Variance Reductioncited by 4
  15. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 4
  16. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  17. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  18. 2024Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradientscited by 3
  19. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  20. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 3
  21. 2021Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applicationscited by 2
  22. 2022Variance-Reduced Conservative Policy Iterationcited by 2
  23. 2024Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learningcited by 2
  24. 2024Boosting the Performance of Decentralized Federated Learning via Catalyst Accelerationcited by 2
  25. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  26. 2021Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programmingcited by 1
  27. 2022On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regressioncited by 1
  28. 2022SADAM: Stochastic Adam, A Stochastic Operator for First-Order Gradient-based Optimizercited by 1
  29. 2023CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexitycited by 1
  30. 2024OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancementcited by 1
  31. 2021Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growthcited by 0
  32. 2022Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexitycited by 0
  33. 2023Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimizationcited by 0
  34. 2023Ordering for Non-Replacement SGDcited by 0
  35. 2024A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithmcited by 0
  36. 2024Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithmscited by 0
  37. 2025HOME-3: High-Order Momentum Estimator with Third-Power Gradient for Convex and Smooth Nonconvex Optimizationcited by 0
  38. 2025Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Studycited by 0

50 most cited of 54 All 54 (JSON)