mlsanityData to 7 Oct 2026

A unified variance-reduced accelerated gradient method for convex optimization

arXiv 1905.12412 ↗First posted 29 May 2019math.OC cs.DS cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

We propose a novel randomized incremental gradient algorithm, namely, VAriance-Reduced Accelerated Gradient (Varag), for finite-sum optimization. Equipped with a unified step-size policy that adjusts itself to the value of the condition number, Varag exhibits the unified optimal rates of convergence for solving smooth convex finite-sum problems directly regardless of their strong convexity. Moreover, Varag is the first accelerated randomized incremental gradient method that benefits from the strong convexity of the data-fidelity term to achieve the optimal linear convergence. It also establishes an optimal linear rate of convergence for solving a wide class of problems only satisfying a certain error bound condition rather than strong convexity. Varag can also be extended to solve stochastic finite-sum problems.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 10; 2022: 7; 2023: 3; 2024: 2; 2025: 1.

23 papers.

Sort:

  1. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  2. 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
  3. 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
  4. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  5. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  6. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  7. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  8. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  9. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  10. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  11. 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
  12. 2021Stochastic Reweighted Gradient Descentcited by 7
11 more
  1. 2023Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothnesscited by 7
  2. 2021EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedbackcited by 6
  3. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  4. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  5. 2022Adaptive Accelerated (Extra-)Gradient Methods with Variance Reductioncited by 4
  6. 2024Correlated Quantization for Faster Nonconvex Distributed Optimizationcited by 3
  7. 2021An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimizationcited by 1
  8. 2025First-order methods for stochastic and finite-sum convex optimization with deterministic constraintscited by 1
  9. 2021Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimizationcited by 0
  10. 2022Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Topcited by 0
  11. 2024Efficient Continual Finite-Sum Minimizationcited by 0