# ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 49 references that are in the map.
- First posted on arXiv 21 Mar 2021.

## Builds on (most cited first, 30 of 32)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1802.04477/) (2018)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization](https://mlsanity.com/paper/2006.07013/) (2020)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method](https://mlsanity.com/paper/1609.03261/) (2016)
- [Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1905.00529/) (2019)
- [Random gradient extrapolation for distributed and stochastic optimization](https://mlsanity.com/paper/1711.05762/) (2017)

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

- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback](https://mlsanity.com/paper/2110.03294/) (2021)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [Personalized Federated Learning with Multiple Known Clusters](https://mlsanity.com/paper/2204.13619/) (2022)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)

## Abstract (arXiv)

In this paper, we propose a novel accelerated gradient method called ANITA for solving the fundamental finite-sum optimization problems. Concretely, we consider both general convex and strongly convex settings: i) For general convex finite-sum problems, ANITA improves previous state-of-the-art result given by Varag (Lan et al., 2019). In particular, for large-scale problems or the convergence error is not very small, i.e., n ≥ frac1ε2, ANITA obtains the first optimal result O(n), matching the lower bound Omega(n) provided by Woodworth and Srebro (2016), while previous results are O(n log frac1ε) of Varag (Lan et al., 2019) and O(fracn√ε) of Katyusha (Allen-Zhu, 2017). ii) For strongly convex finite-sum problems, we also show that ANITA can achieve the optimal convergence rate Obig((n+√fracnLμ)logfrac1εbig) matching the lower bound Omegabig((n+√fracnLμ)logfrac1εbig) provided by Lan and Zhou (2015). Besides, ANITA enjoys a simpler loopless algorithmic structure unlike previous accelerated algorithms such as Varag (Lan et al., 2019) and Katyusha (Allen-Zhu, 2017) where they use double-loop structures. Moreover, we provide a novel dynamic multi-stage convergence analysis, which is the key technical part for improving previous results to the optimal rates. We believe that our new theoretical rates and novel convergence analysis for the fundamental finite-sum problem will directly lead to key improvements for many other related problems, such as distributed/federated/decentralized optimization problems (e.g., Li and Richt'arik, 2021). Finally, the numerical experiments show that ANITA converges faster than the previous state-of-the-art Varag (Lan et al., 2019), validating our theoretical results and confirming the practical superiority of ANITA.