mlsanityData to 7 Oct 2026

Coordinating Distributed Example Orders for Provably Accelerated Training

arXiv 2302.00845 ↗First posted 2 Feb 2023cs.LG cs.DC math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

Recent research on online Gradient Balancing (GraB) has revealed that there exist permutation-based example orderings for SGD that are guaranteed to outperform random reshuffling (RR). Whereas RR arbitrarily permutes training examples, GraB leverages stale gradients from prior epochs to order examples -- achieving a provably faster convergence rate than RR. However, GraB is limited by design: while it demonstrates an impressive ability to scale-up training on centralized data, it does not naturally extend to modern distributed ML workloads. We therefore propose Coordinated Distributed GraB (CD-GraB), which uses insights from prior work on kernel thinning to translate the benefits of provably faster permutation-based example ordering to distributed settings. With negligible overhead, CD-GraB exhibits a linear speedup in convergence rate over centralized GraB and outperforms distributed RR on a variety of benchmark tasks.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 30 of its 54 references that are in the map. First posted on arXiv 2 Feb 2023.

Builds on

30 of 54 references.

References · 30

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,854
  4. 2016Pointer Sentinel Mixture Modelscited by 2,992
  5. 2017Don't Decay the Learning Rate, Increase the Batch Sizecited by 313
  6. 2021Curriculum Learning: A Surveycited by 257
  7. 2017Automated Curriculum Learning for Neural Networkscited by 251
  8. 2017Regularizing and Optimizing LSTM Language Modelscited by 205
  9. 2017Teacher-Student Curriculum Learningcited by 197
  10. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  11. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  12. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
18 more
  1. 2016Tying Word Vectors and Word Classifiers: A Loss Framework for Language Modelingcited by 87
  2. 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
  3. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  4. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  5. 2021Kernel Thinningcited by 47
  6. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
  7. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  8. 2021Generalized Kernel Thinningcited by 29
  9. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 26
  10. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  11. 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
  12. 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
  13. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  14. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  15. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  16. 2022Targeted Separation and Convergence with Kernel Discrepanciescited by 15
  17. 2021Variance Reduced Training with Stratified Sampling for Forecasting Modelscited by 13
  18. 2021Distributed Random Reshuffling over Networkscited by 6

Built on by

Cited by year (2026 to 7 Oct)

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

7 papers.

  1. 2025SonicMoE: Accelerating MoE with IO and Tile-aware Optimizationscited by 20
  2. 2024Machine Unlearning Doesn't Do What You Think: Lessons for Generative AI Policy and Researchcited by 14
  3. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  4. 2025Low-Rank Thinningcited by 7
  5. 2024Efficient and Accurate Explanation Estimation with Distribution Compressioncited by 4
  6. 2023GraB-sampler: Optimal Permutation-based SGD Data Sampler for PyTorchcited by 0
  7. 2026When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structurecited by 0