# Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders arXiv: https://arxiv.org/abs/2104.12112 ยท HTML: https://mlsanity.com/paper/2104.12112/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 26 of its 40 references that are in the map. - First posted on arXiv 25 Apr 2021. ## Builds on (most cited first, 26 of 26) - [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) - [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) - [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014) - [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015) - [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) - [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019) - [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020) - [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014) - [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021) - [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) - [Stochastic Learning under Random Reshuffling with Constant Step-sizes](https://mlsanity.com/paper/1803.07964/) (2018) - [Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate](https://mlsanity.com/paper/1611.00347/) (2016) - [Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods](https://mlsanity.com/paper/1608.01713/) (2016) - [Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems](https://mlsanity.com/paper/1407.2710/) (2014) - [Linear Convergence of Cyclic SAGA](https://mlsanity.com/paper/1810.11167/) (2018) - [Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications](https://mlsanity.com/paper/1611.02456/) (2016) - [General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Scheme](https://mlsanity.com/paper/1910.05093/) (2019) - [Scaled Relative Graph: Nonexpansive operators via 2D Euclidean Geometry](https://mlsanity.com/paper/1902.09788/) (2019) - [MISO is Making a Comeback With Better Proofs and Rates](https://mlsanity.com/paper/1906.01474/) (2019) - [Understanding the Impact of Model Incoherence on Convergence of Incremental SGD with Random Reshuffle](https://mlsanity.com/paper/2007.03509/) (2020) - [A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Method](https://mlsanity.com/paper/1611.08022/) (2016) - [Tight Coefficients of Averaged Operators via Scaled Relative Graph](https://mlsanity.com/paper/1912.01593/) (2019) ## Built on by (most cited first, 13 of 13) - [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022) - [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021) - [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021) - [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023) - [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021) - [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023) - [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024) - [Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling](https://mlsanity.com/paper/2502.14648/) (2025) - [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024) - [Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness](https://mlsanity.com/paper/2212.01848/) (2022) - [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024) - [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025) - [Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees](https://mlsanity.com/paper/2509.04133/) (2025) ## Abstract (arXiv) When applying a stochastic algorithm, one must choose an order to draw samples. The practical choices are without-replacement sampling orders, which are empirically faster and more cache-friendly than uniform-iid-sampling but often have inferior theoretical guarantees. Without-replacement sampling is well understood only for SGD without variance reduction. In this paper, we will improve the convergence analysis and rates of variance reduction under without-replacement sampling orders for composite finite-sum minimization. Our results are in two-folds. First, we develop a damped variant of Finito called Prox-DFinito and establish its convergence rates with random reshuffling, cyclic sampling, and shuffling-once, under both convex and strongly convex scenarios. These rates match full-batch gradient descent and are state-of-the-art compared to the existing results for without-replacement sampling with variance-reduction. Second, our analysis can gauge how the cyclic order will influence the rate of cyclic sampling and, thus, allows us to derive the optimal fixed ordering. In the highly data-heterogeneous scenario, Prox-DFinito with optimal cyclic sampling can attain a sample-size-independent convergence rate, which, to our knowledge, is the first result that can match with uniform-iid-sampling with variance reduction. We also propose a practical method to discover the optimal cyclic ordering numerically.