# On the Convergence of SARAH and Beyond

arXiv: https://arxiv.org/abs/1906.02351 · HTML: https://mlsanity.com/paper/1906.02351/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2019.

## Built on by (most cited first, 10 of 10)

- [Enhancing Sharpness-Aware Optimization Through Variance Suppression](https://mlsanity.com/paper/2309.15639/) (2023)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling](https://mlsanity.com/paper/2502.14648/) (2025)
- [Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysis](https://mlsanity.com/paper/2212.09413/) (2022)
- [VASSO: Variance Suppression for Sharpness-Aware Minimization](https://mlsanity.com/paper/2509.02433/) (2025)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)
- [Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization](https://mlsanity.com/paper/2509.00737/) (2025)

## Abstract (arXiv)

The main theme of this work is a unifying algorithm, LoopLess SARAH (L2S) for problems formulated as summation of n individual loss functions. L2S broadens a recently developed variance reduction method known as SARAH. To find an ε-accurate solution, L2S enjoys a complexity of cal Obig( (n+kappa) ln (1/ε)big) for strongly convex problems. For convex problems, when adopting an n-dependent step size, the complexity of L2S is cal O(n+ √n/ε); while for more frequently adopted n-independent step size, the complexity is cal O(n+ n/ε). Distinct from SARAH, our theoretical findings support an n-independent step size in convex problems without extra assumptions. For nonconvex problems, the complexity of L2S is cal O(n+ √n/ε). Our numerical tests on neural networks suggest that L2S can have better generalization properties than SARAH. Along with L2S, our side results include the linear convergence of the last iteration for SARAH in strongly convex problems.