# Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting

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

## 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 (most cited first, 30 of 39)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [On the Convergence Rate of Incremental Aggregated Gradient Algorithms](https://mlsanity.com/paper/1506.02081/) (2015)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [Mini-Batch Primal and Dual Methods for SVMs](https://mlsanity.com/paper/1303.2314/) (2013)
- [Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate](https://mlsanity.com/paper/1611.00347/) (2016)
- [Inexact SARAH Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1811.10105/) (2018)
- [Accelerated Mini-Batch Stochastic Dual Coordinate Ascent](https://mlsanity.com/paper/1305.2581/) (2013)
- [Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods](https://mlsanity.com/paper/1608.01713/) (2016)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [SAGA with Arbitrary Sampling](https://mlsanity.com/paper/1901.08669/) (2019)

## 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.