# Direct Acceleration of SAGA using Sampled Negative Momentum

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

## Key facts

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

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

- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning](https://mlsanity.com/paper/2108.06869/) (2021)
- [Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness](https://mlsanity.com/paper/2302.06032/) (2023)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms](https://mlsanity.com/paper/2205.02273/) (2022)
- [Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size](https://mlsanity.com/paper/2608.12009/) (2026)

## Abstract (arXiv)

Variance reduction is a simple and effective technique that accelerates convex (or non-convex) stochastic optimization. Among existing variance reduction methods, SVRG and SAGA adopt unbiased gradient estimators and are the most popular variance reduction methods in recent years. Although various accelerated variants of SVRG (e.g., Katyusha and Acc-Prox-SVRG) have been proposed, the direct acceleration of SAGA still remains unknown. In this paper, we propose a directly accelerated variant of SAGA using a novel Sampled Negative Momentum (SSNM), which achieves the best known oracle complexity for strongly convex problems (with known strong convexity parameter). Consequently, our work fills the void of directly accelerated SAGA.