Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD

Abstract

Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characterization of the speed-up offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime (wallclock time). The novelty in our work is that our runtime analysis considers random straggler delays, which helps us design and compare distributed SGD algorithms that strike a balance between stragglers and staleness. We also present a new convergence analysis of asynchronous SGD variants without bounded or exponential delay assumptions, and a novel learning rate schedule to compensate for gradient staleness.

Single Column Version, 33 pages, 14 figures, Accepted at AISTATS 2018

References in corpus (3)

• An overview of gradient descent optimization algorithms
• Asynchronous Coordinate Descent under More Realistic Assumptions
• Gradient Diversity: a Key Ingredient for Scalable Distributed Learning

Cited by in corpus (15)

• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Robust and Communication-Efficient Collaborative Learning
• Diversity/Parallelism Trade-off in Distributed Systems with Redundancy
• Speeding up Deep Learning with Transient Servers
• Making Asynchronous Stochastic Gradient Descent Work for Transformers
• Consistent Lock-free Parallel Stochastic Gradient Descent for Fast and Stable Convergence
• Gap Aware Mitigation of Gradient Staleness
• Distributed SGD Generalizes Well Under Asynchrony
• Trade-offs of Local SGD at Scale: An Empirical Study