Coordinating Distributed Example Orders for Provably Accelerated Training

2023/02/02 by Cooper, A. Feder, Guo, Wentao, Pham, Khiem +4 · 1 citation
#Distributed #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2302.00845

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.

Cited by

• SonicMoE: Accelerating MoE with IO and Tile-aware Optimizations

Related

• GraB: Finding Provably Better Data Permutations than Random Reshuffling
• Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods
• Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
• Scaling Distributed Training with Adaptive Summation
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it