mlsanityData to 7 Oct 2026

Closing the convergence gap of SGD without replacement

arXiv 2002.10400 ↗First posted 24 Feb 2020cs.LG math.OC stat.MLcited by 56

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent without replacement sampling is widely used in practice for model training. However, the vast majority of SGD analyses assumes data is sampled with replacement, and when the function minimized is strongly convex, an Oleft(frac1Tright) rate can be established when SGD is run for T iterations. A recent line of breakthrough works on SGD without replacement (SGDo) established an Oleft(fracnT2right) convergence rate when the function minimized is strongly convex and is a sum of n smooth functions, and an Oleft(frac1T2+fracn3T3right) rate for sums of quadratics. On the other hand, the tightest known lower bound postulates an Omegaleft(frac1T2+fracn2T3right) rate, leaving open the possibility of better SGDo convergence rates in the general case. In this paper, we close this gap and show that SGD without replacement achieves a rate of Oleft(frac1T2+fracn2T3right) when the sum of the functions is a quadratic, and offer a new lower bound of Omegaleft(fracnT2right) for strongly convex functions that are sums of smooth functions.

Key facts. Cited by 56 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 13; 2023: 10; 2024: 7; 2025: 9; 2026: 9.

56 papers.

Sort:

  1. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  2. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  3. 2021Random Reshuffling with Variance Reduction: New Analysis and Better Ratescited by 19
  4. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  5. 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
  6. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  7. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  8. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  9. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 16
  10. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  11. 2022Adaptive Compression for Communication-Efficient Distributed Trainingcited by 14
  12. 2021Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orderscited by 13
38 more
  1. 2022Federated Random Reshuffling with Compression and Variance Reductioncited by 11
  2. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  3. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  4. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  5. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 10
  6. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  7. 2021Optimal Rates for Random Order Online Optimizationcited by 9
  8. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 9
  9. 2021Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?cited by 8
  10. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  11. 2023Mini-Batch Optimization of Contrastive Losscited by 8
  12. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  13. 2025Low-Rank Thinningcited by 7
  14. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  15. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  16. 2026Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noisecited by 6
  17. 2023High Probability Guarantees for Random Reshufflingcited by 5
  18. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  19. 2023On the Training Instability of Shuffling SGD with Batch Normalizationcited by 3
  20. 2024Asynchronous Federated Learning: A Scalable Approach for Decentralized Machine Learningcited by 3
  21. 2022Stochastic Gradient Descent without Full Data Shufflecited by 2
  22. 2022Sequential Gradient Descent and Quasi-Newton's Method for Change-Point Analysiscited by 2
  23. 2023Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimizationcited by 2
  24. 2025Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimizationcited by 2
  25. 2026Process-Tensor Tomography of SGD: Measuring Non-Markovian Memory via Back-Flow of Distinguishabilitycited by 2
  26. 2022Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysiscited by 1
  27. 2023Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Conditioncited by 1
  28. 2024Shuffling Momentum Gradient Algorithm for Convex Optimizationcited by 1
  29. 2025Experience Replay with Random Reshufflingcited by 1
  30. 2026Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimizationcited by 1
  31. 2026Random Reshuffling Dominates Stochastic Gradient Descentcited by 1
  32. 2022Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothnesscited by 0
  33. 2023Ordering for Non-Replacement SGDcited by 0
  34. 2024Error dynamics of mini-batch gradient descent with random reshuffling for least squares regressioncited by 0
  35. 2024Loss Gradient Gaussian Width based Generalization and Optimization Guaranteescited by 0
  36. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0
  37. 2025Proto-EVFL: Enhanced Vertical Federated Learning via Dual Prototype with Extremely Unaligned Datacited by 0
  38. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0

50 most cited of 56 All 56 (JSON)