# Acceleration Methods

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2021.

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

- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [Preconditioning Benefits of Spectral Orthogonalization in Muon](https://mlsanity.com/paper/2601.13474/) (2026)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [The Curse of Unrolling: Rate of Differentiating Through Optimization](https://mlsanity.com/paper/2209.13271/) (2022)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Rethinking Initialization of the Sinkhorn Algorithm](https://mlsanity.com/paper/2206.07630/) (2022)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Accelerating optimization over the space of probability measures](https://mlsanity.com/paper/2310.04006/) (2023)
- [Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time](https://mlsanity.com/paper/2207.02189/) (2022)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Sum-of-Squares Relaxations for Information Theory and Variational Inference](https://mlsanity.com/paper/2206.13285/) (2022)
- [Sequential Counterfactual Risk Minimization](https://mlsanity.com/paper/2302.12120/) (2023)
- [Riemannian accelerated gradient methods via extrapolation](https://mlsanity.com/paper/2208.06619/) (2022)
- [Open Problem: Anytime Convergence Rate of Gradient Descent](https://mlsanity.com/paper/2406.13888/) (2024)
- [Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/2502.11229/) (2025)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization](https://mlsanity.com/paper/2205.12751/) (2022)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization](https://mlsanity.com/paper/2402.08097/) (2024)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Enhancing Privacy in Federated Learning through Local Training](https://mlsanity.com/paper/2403.17572/) (2024)
- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)

## Abstract (arXiv)

This monograph covers some recent advances in a range of acceleration techniques frequently used in convex optimization. We first use quadratic optimization problems to introduce two key families of methods, namely momentum and nested optimization schemes. They coincide in the quadratic case to form the Chebyshev method. We discuss momentum methods in detail, starting with the seminal work of Nesterov and structure convergence proofs using a few master templates, such as that for optimized gradient methods, which provide the key benefit of showing how momentum methods optimize convergence guarantees. We further cover proximal acceleration, at the heart of the Catalyst and Accelerated Hybrid Proximal Extragradient frameworks, using similar algorithmic patterns. Common acceleration techniques rely directly on the knowledge of some of the regularity parameters in the problem at hand. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates while adapting to unobserved regularity parameters.