# On Tight Convergence Rates of Without-replacement SGD

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2020.

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

- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Better Methods and Theory for Federated Learning: Compression, Client Selection and Heterogeneity](https://mlsanity.com/paper/2207.00392/) (2022)

## Abstract (arXiv)

For solving finite-sum optimization problems, SGD without replacement sampling is empirically shown to outperform SGD. Denoting by n the number of components in the cost and K the number of epochs of the algorithm , several recent works have shown convergence rates of without-replacement SGD that have better dependency on n and K than the baseline rate of O(1/(nK)) for SGD. However, there are two main limitations shared among those works: the rates have extra poly-logarithmic factors on nK, and denoting by kappa the condition number of the problem, the rates hold after kappaclog(nK) epochs for some c>0. In this work, we overcome these limitations by analyzing step sizes that vary across epochs.