# Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 45 references that are in the map.
- First posted on arXiv 28 Jan 2022.

## Builds on (most cited first, 28 of 28)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise](https://mlsanity.com/paper/1902.01637/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities](https://mlsanity.com/paper/2007.08840/) (2020)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)
- [Random gradient extrapolation for distributed and stochastic optimization](https://mlsanity.com/paper/1711.05762/) (2017)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence](https://mlsanity.com/paper/2010.07799/) (2020)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Almost Tune-Free Variance Reduction](https://mlsanity.com/paper/1908.09345/) (2019)

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

- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [A regret minimization approach to fixed-point iterations](https://mlsanity.com/paper/2509.21653/) (2025)

## Abstract (arXiv)

In this paper, we study the finite-sum convex optimization problem focusing on the general convex case. Recently, the study of variance reduced (VR) methods and their accelerated variants has made exciting progress. However, the step size used in the existing VR algorithms typically depends on the smoothness parameter, which is often unknown and requires tuning in practice. To address this problem, we propose two novel adaptive VR algorithms: Adaptive Variance Reduced Accelerated Extra-Gradient (AdaVRAE) and Adaptive Variance Reduced Accelerated Gradient (AdaVRAG). Our algorithms do not require knowledge of the smoothness parameter. AdaVRAE uses Oleft(nloglog n+√fracnβεright) gradient evaluations and AdaVRAG uses Oleft(nloglog n+√fracnβlogβεright) gradient evaluations to attain an O(ε)-suboptimal solution, where n is the number of functions in the finite sum and β is the smoothness parameter. This result matches the best-known convergence rate of non-adaptive VR methods and it improves upon the convergence of the state of the art adaptive VR method, AdaSVRG. We demonstrate the superior performance of our algorithms compared with previous methods in experiments on real-world datasets.