mlsanityData to 14 Oct 2026

Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization

arXiv 2211.01851 ↗First posted 3 Nov 2022math.OC cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

We propose an adaptive variance-reduction method, called AdaSpider, for minimization of L-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan & Streeter, 2010], but a fairly distinct, adaptive step-size schedule with the recursive stochastic path integrated estimator proposed in [Fang et al., 2018]. To our knowledge, Adaspider is the first parameter-free non-convex variance-reduction method in the sense that it does not require the knowledge of problem-dependent parameters, such as smoothness constant L, target accuracy ε or any bound on gradient norms. In doing so, we are able to compute an ε-stationary point with tildeOleft(n + √n/ε2right) oracle-calls, which matches the respective lower bound up to logarithmic factors.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 37 of its 58 references that are in the map. First posted on arXiv 3 Nov 2022.

Builds on

37 of 58 references.

References · 37

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  3. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,070
  4. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  6. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  7. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  9. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  10. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  11. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  12. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
25 more
  1. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  2. 2020Lipschitz constant estimation of Neural Networks via sparse polynomial optimizationcited by 87
  3. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  4. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  5. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  6. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  7. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  8. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  9. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  10. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  11. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  12. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  13. 2016Barzilai-Borwein Step Size for Stochastic Gradient Descentcited by 33
  14. 2018A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimizationcited by 33
  15. 2015Scale-Free Algorithms for Online Linear Optimizationcited by 30
  16. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  17. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 29
  18. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 24
  19. 2020Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimizationcited by 19
  20. 2020Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalitiescited by 18
  21. 2018Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimizationcited by 15
  22. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  23. 2017Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parametercited by 8
  24. 2019Almost Tune-Free Variance Reductioncited by 7
  25. 2022Adaptive Accelerated (Extra-)Gradient Methods with Variance Reductioncited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 6; 2025: 3; 2026: 1.

15 papers.

Sort:

  1. 2024MARS: Unleashing the Power of Variance Reduction for Training Large Modelscited by 64
  2. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  3. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  4. 2023Variance-reduced Clipping for Non-convex Optimizationcited by 22
  5. 2023Dropout Reduces Underfittingcited by 21
  6. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  7. 2025MARS-M: When Variance Reduction Meets Matricescited by 10
  8. 2023A Coefficient Makes SVRG Effectivecited by 7
  9. 2025How Effective Can Dropout Be in Multiple Instance Learning ?cited by 7
  10. 2024Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptionscited by 6
  11. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  12. 2024Faster Adaptive Decentralized Learning Algorithmscited by 1
3 more
  1. 2025Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1
  2. 2024Efficient Continual Finite-Sum Minimizationcited by 0
  3. 2026Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Sizecited by 0