mlsanityData to 14 Oct 2026

Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting

arXiv 2506.12444 ↗First posted 14 Jun 2025math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose Adjusted Shuffling SARAH, a novel algorithm that integrates shuffling strategies into the recursive SARAH framework using a dynamic weighting mechanism to enhance exploration. We analyze the algorithm under two operating modes. First, we show that the Exact Mode matches the best-known theoretical guarantees for shuffling variance-reduced methods in both strongly convex and non-convex settings. Second, to address large-scale regimes, we introduce an Inexact Mode that utilizes mini-batch estimators. A key contribution of our work is proving that this Inexact Mode achieves a total complexity independent of the dataset size, making it significantly more scalable than existing shuffling methods when the sample size is large.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 39 of its 63 references that are in the map. First posted on arXiv 14 Jun 2025.

Builds on

39 of 63 references.

References · 39

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  6. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  7. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  8. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  9. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  10. 2019How Good is SGD with Random Shuffling?cited by 64
  11. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  12. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
27 more
  1. 2020Closing the convergence gap of SGD without replacementcited by 57
  2. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  3. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  4. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
  5. 2014Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningcited by 35
  6. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 27
  7. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  8. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 22
  9. 2015On the Convergence Rate of Incremental Aggregated Gradient Algorithmscited by 21
  10. 2021Random Reshuffling with Variance Reduction: New Analysis and Better Ratescited by 19
  11. 2021Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orderscited by 13
  12. 2013Mini-Batch Primal and Dual Methods for SVMscited by 12
  13. 2016Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Ratecited by 12
  14. 2018Inexact SARAH Algorithm for Stochastic Optimizationcited by 12
  15. 2013Accelerated Mini-Batch Stochastic Dual Coordinate Ascentcited by 11
  16. 2016Global Convergence Rate of Proximal Incremental Aggregated Gradient Methodscited by 11
  17. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  18. 2019SAGA with Arbitrary Samplingcited by 10
  19. 2019On the Convergence of SARAH and Beyondcited by 10
  20. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  21. 2018Linear Convergence of Cyclic SAGAcited by 9
  22. 2021Random-reshuffled SARAH does not need a full gradient computationscited by 7
  23. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  24. 2024Learning-rate-free Momentum SGD with Reshuffling Converges in Nonsmooth Nonconvex Optimizationcited by 4
  25. 2025Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shufflingcited by 2
  26. 2024Shuffling Momentum Gradient Algorithm for Convex Optimizationcited by 1
  27. 2024Shuffling Gradient Descent-Ascent with Variance Reduction for Nonconvex-Strongly Concave Smooth Minimax Problemscited by 1

Built on by

Not cited yet.