mlsanityData to 7 Oct 2026

Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods

arXiv 2202.01838 ↗First posted 3 Feb 2022cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

While SGD, which samples from the data with replacement is widely studied in theory, a variant called Random Reshuffling (RR) is more common in practice. RR iterates through random permutations of the dataset and has been shown to converge faster than SGD. When the order is chosen deterministically, a variant called incremental gradient descent (IG), the existing convergence bounds show improvement over SGD but are worse than RR. However, these bounds do not differentiate between a good and a bad ordering and hold for the worst choice of order. Meanwhile, in some cases, choosing the right order when using IG can lead to convergence faster than RR. In this work, we quantify the effect of order on convergence speed, obtaining convergence bounds based on the chosen sequence of permutations while also recovering previous results for RR. In addition, we show benefits of using structured shuffling when various levels of abstractions (e.g. tasks, classes, augmentations, etc.) exists in the dataset in theory and in practice. Finally, relying on our measure, we develop a greedy algorithm for choosing good orders during training, achieving superior performance (by more than 14 percent in accuracy) over RR.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 21 of its 33 references that are in the map. First posted on arXiv 3 Feb 2022.

Builds on

21 of 33 references.

References · 21

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  6. 2018Not All Samples Are Created Equal: Deep Learning with Importance Samplingcited by 323
  7. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  8. 2015Variance Reduction in SGD by Distributed Importance Samplingcited by 79
  9. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  10. 2021Manipulating SGD with Data Ordering Attackscited by 73
  11. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  12. 2019How Good is SGD with Random Shuffling?cited by 63
9 more
  1. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
  2. 2020Closing the convergence gap of SGD without replacementcited by 56
  3. 2018A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updatescited by 47
  4. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  5. 2020Choosing the Sample with Lowest Loss makes SGD Robustcited by 26
  6. 2017Safe Adaptive Importance Samplingcited by 19
  7. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  8. 2021Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updatescited by 16
  9. 2016Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 7; 2024: 4; 2025: 1; 2026: 2.

15 papers.

Sort:

  1. 2023On The Impact of Machine Learning Randomness on Group Fairnesscited by 26
  2. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  3. 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
  4. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  5. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 9
  6. 2023Coordinating Distributed Example Orders for Provably Accelerated Trainingcited by 7
  7. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  8. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  9. 2024Understanding the Training Speedup from Sampling with Approximate Lossescited by 2
  10. 2026TideGS: Scalable Training of Over One Billion 3D Gaussian Splatting Primitives via Out-of-Core Optimizationcited by 2
  11. 2024Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Samplingcited by 1
  12. 2023Ordering for Non-Replacement SGDcited by 0
3 more
  1. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  2. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0
  3. 2026CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedulescited by 0