# Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2020.

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

- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [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)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [First-order methods for stochastic and finite-sum convex optimization with deterministic constraints](https://mlsanity.com/paper/2506.20630/) (2025)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [Efficient Continual Finite-Sum Minimization](https://mlsanity.com/paper/2406.04731/) (2024)
- [Optimal Oracle Complexity for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2610.05038/) (2026)

## Abstract (arXiv)

In this paper, we introduce a simplified and unified method for finite-sum convex optimization, named Variance Reduction via Accelerated Dual Averaging (VRADA). In both general convex and strongly convex settings, VRADA can attain an Obig(frac1nbig)-accurate solution in O(nloglog n) number of stochastic gradient evaluations which improves the best-known result O(nlog n), where n is the number of samples. Meanwhile, VRADA matches the lower bound of the general convex setting up to a loglog n factor and matches the lower bounds in both regimes n≤ Theta(kappa) and ngg kappa of the strongly convex setting, where kappa denotes the condition number. Besides improving the best-known results and matching all the above lower bounds simultaneously, VRADA has more unified and simplified algorithmic implementation and convergence analysis for both the general convex and strongly convex settings. The underlying novel approaches such as the novel initialization strategy in VRADA may be of independent interest. Through experiments on real datasets, we show the good performance of VRADA over existing methods for large-scale machine learning problems.