mlsanityData to 7 Oct 2026

Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions

arXiv 2406.01959 ↗First posted 4 Jun 2024math.OC cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

This paper explores adaptive variance reduction methods for stochastic optimization based on the STORM technique. Existing adaptive extensions of STORM rely on strong assumptions like bounded gradients and bounded function values, or suffer an additional O(log T) term in the convergence rate. To address these limitations, we introduce a novel adaptive STORM method that achieves an optimal convergence rate of O(T-1/3) for non-convex functions with our newly designed learning rate strategy. Compared with existing approaches, our method requires weaker assumptions and attains the optimal convergence rate without the additional O(log T) term. We also extend the proposed technique to stochastic compositional optimization, obtaining the same optimal rate of O(T-1/3). Furthermore, we investigate the non-convex finite-sum problem and develop another innovative adaptive variance reduction method that achieves an optimal convergence rate of O(n1/4 T-1/2 ), where n represents the number of component functions. Numerical experiments across various tasks validate the effectiveness of our method.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 31 of its 45 references that are in the map. First posted on arXiv 4 Jun 2024.

Builds on

31 of 45 references.

References · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  6. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  7. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  8. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  9. 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 282
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  11. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  12. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
19 more
  1. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  2. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  3. 2022Making SGD Parameter-Freecited by 50
  4. 2020Faster Non-Convex Federated Learning via Global and Local Momentumcited by 48
  5. 2016Accelerating Stochastic Composition Optimizationcited by 46
  6. 2020An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectivescited by 42
  7. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  8. 2019Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimizationcited by 31
  9. 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
  10. 2014Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learningcited by 27
  11. 2019A Stochastic Composite Gradient Method with Incremental Variance Reductioncited by 26
  12. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  13. 2020Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Bettingcited by 19
  14. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  15. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  16. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  17. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  18. 2022META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functionscited by 5
  19. 2023Learning Unnormalized Statistical Models via Compositional Optimizationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 4.

5 papers.

  1. 2026JacQuant: STE-Free Quantization-Aware Training via Learned Jacobian Surrogatescited by 2
  2. 2025Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1
  3. 2026OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimalitycited by 1
  4. 2026OptEMA: Adaptive Exponential Moving Average for Stochastic Optimization with Zero-Noise Optimalitycited by 0
  5. 2026Convergence Analysis of STORM Under Different Geometriescited by 0