# A Generic Acceleration Framework for Stochastic Composite Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 9 of 9)

- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization](https://mlsanity.com/paper/2110.09057/) (2021)
- [On the Performance Analysis of Momentum Method: A Frequency Domain Perspective](https://mlsanity.com/paper/2411.19671/) (2024)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regression](https://mlsanity.com/paper/2204.07702/) (2022)
- [Adaptive Strategies in Non-convex Optimization](https://mlsanity.com/paper/2306.10278/) (2023)

## Abstract (arXiv)

In this paper, we introduce various mechanisms to obtain accelerated first-order stochastic optimization algorithms when the objective function is convex or strongly convex. Specifically, we extend the Catalyst approach originally designed for deterministic objectives to the stochastic setting. Given an optimization method with mild convergence guarantees for strongly convex problems, the challenge is to accelerate convergence to a noise-dominated region, and then achieve convergence with an optimal worst-case complexity depending on the noise variance of the gradients. A side contribution of our work is also a generic analysis that can handle inexact proximal operators, providing new insights about the robustness of stochastic algorithms when the proximal operator cannot be exactly computed.