CD-GraB: Coordinating Distributed Example Orders for Provably Accelerated Training

A. F. Cooper, Wentao Guo, Khiem Pham, Tiancheng Yuan, Charlie F. Ruan +2 more
2/1/2023

No official code found. Best implementation: GarlGuo/CD-GraB (5 stars, PyTorch, last commit 2024-09-17).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

GarlGuo/CD-GraBCommunity53%
PyTorch

CD-GraB is a distributed gradient balancing framework that aims to find distributed data permutation with provably better convergence guarantees than Distributed Random Reshuffling (D-RR). https://arxiv.org/pdf/2302.00845.pdf.

50Python, Jupyter NotebookFeb 5, 20232 years agoNOASSERTION
distributed-learningdistributed-random-reshufflingoptimizationpytorch

Similar Papers

GraB: Finding Provably Better Data Permutations than Random Reshuffling

85% match1 repo62022

Corgi^2: A Hybrid Offline-Online Approach To Storage-Aware Data Shuffling For SGD

80% match2023

M-L2O: Towards Generalizable Learning-to-Optimize by Test-Time Fast Self-Adaptation

79% match1 repo62023

Adaptively Sampling-Reusing-Mixing Decomposed Gradients to Speed Up Sharpness Aware Minimization

79% match2025

3DGS$^2$: Near Second-order Converging 3D Gaussian Splatting

79% match2025

SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

79% match1 repo1.1k2019

Cite this paper

@article{cooper2023cdgrab,
  title  = {CD-GraB: Coordinating Distributed Example Orders for Provably Accelerated Training},
  author = {A. F. Cooper and Wentao Guo and Khiem Pham and Tiancheng Yuan and Charlie F. Ruan and Yucheng Lu and Chris De Sa},
  year   = {2023},
  eprint = {2302.00845},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2302.00845},
  journal = {NEURIPS 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2302.00845.svg)](https://codeofpaper.com/paper/2302.00845)

Discussion