mlsanityData to 14 Oct 2026

Random-reshuffled SARAH does not need a full gradient computations

arXiv 2111.13322 ↗First posted 26 Nov 2021cs.LG math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

The StochAstic Recursive grAdient algoritHm (SARAH) algorithm is a variance reduced variant of the Stochastic Gradient Descent (SGD) algorithm that needs a gradient of the objective function from time to time. In this paper, we remove the necessity of a full gradient computation. This is achieved by using a randomized reshuffling strategy and aggregating stochastic gradients obtained in each epoch. The aggregated stochastic gradients serve as an estimate of a full gradient in the SARAH algorithm. We provide a theoretical analysis of the proposed approach and conclude the paper with numerical experiments that demonstrate the efficiency of this approach.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 39 of its 57 references that are in the map. First posted on arXiv 26 Nov 2021.

Builds on

39 of 57 references.

References · 39

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  3. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  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. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  9. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  10. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  11. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  12. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
27 more
  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  2. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  3. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  4. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  5. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  6. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  7. 2014Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningcited by 35
  8. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  9. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 30
  10. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 29
  11. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  12. 2015On the Convergence Rate of Incremental Aggregated Gradient Algorithmscited by 21
  13. 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
  14. 2018On Acceleration with Noise-Corrupted Gradientscited by 20
  15. 2021Random Reshuffling with Variance Reduction: New Analysis and Better Ratescited by 19
  16. 2018Stochastic Learning under Random Reshuffling with Constant Step-sizescited by 15
  17. 2021Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orderscited by 13
  18. 2013Mini-Batch Primal and Dual Methods for SVMscited by 12
  19. 2016Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Ratecited by 12
  20. 2018Inexact SARAH Algorithm for Stochastic Optimizationcited by 12
  21. 2019SAGA with Arbitrary Samplingcited by 10
  22. 2019On the Convergence of SARAH and Beyondcited by 10
  23. 2020An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimizationcited by 10
  24. 2018Linear Convergence of Cyclic SAGAcited by 9
  25. 2019General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Schemecited by 6
  26. 2019Accelerating Mini-batch SARAH by Step Size Rulescited by 4
  27. 2016A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Methodcited by 3

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 2; 2025: 2.

7 papers.

  1. 2023Federated Learning with Regularized Client Participationcited by 14
  2. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  3. 2022On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithmscited by 2
  4. 2025Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shufflingcited by 2
  5. 2022Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learningcited by 0
  6. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  7. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0