# A Simple Practical Accelerated Method for Finite Sums

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2016.

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

- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [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)
- [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)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation](https://mlsanity.com/paper/2302.09832/) (2023)
- [A Unified Theory of Stochastic Proximal Point Methods without Smoothness](https://mlsanity.com/paper/2405.15941/) (2024)
- [Variance reduction techniques for stochastic proximal point algorithms](https://mlsanity.com/paper/2308.09310/) (2023)
- [Efficient algorithms for implementing incremental proximal-point methods](https://mlsanity.com/paper/2205.01457/) (2022)
- [On the SAGA algorithm with decreasing step](https://mlsanity.com/paper/2410.03760/) (2024)
- [An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms](https://mlsanity.com/paper/2205.02273/) (2022)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)

## Abstract (arXiv)

We describe a novel optimization method for finite sums (such as empirical risk minimization problems) building on the recently introduced SAGA method. Our method achieves an accelerated convergence rate on strongly convex smooth problems. Our method has only one parameter (a step size), and is radically simpler than other accelerated methods for finite sums. Additionally it can be applied when the terms are non-smooth, yielding a method applicable in many areas where operator splitting methods would traditionally be applied.