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

By Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, Priya Nagpurkar. 2018

217 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture, Optimization & Training, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Hardware and Architecture

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “Theoretical and empirical analysis (Dutta et al., 2018) suggests that synchronous training is more stable with less noise, but can also be slowed down by the global barrier across all the workers.”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Communication overhead is a major issue limiting the scaling of this approach, since ALLREDUCE must complete before every step and blocking communications are sensitive to stragglers (Dutta et al., 2018; Ferdinand et al., 2019).”
Robust and Communication-Efficient Collaborative Learning (2019, background): “Another line of work proposes asynchronous decentralized SGD, where the workers update their models based on the last iterates received by their neighbors (Recht et al., 2011; Lian et al., 2017b; Lan and Zhou, 2018; Peng et al., 2016; Wu et al., 2017; Dutta et al., 2018).”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “Only a few previous works explore the second factor from a theoretical perspective, see [6, 7] — these works consider the centralized parameter server model.”
Zeno++: Robust Fully Asynchronous SGD (2019, background): “Theoretical and experimental analysis (Dutta et al., 2018) suggests that synchronous training is more stable and has lower noise, but is slower due to the global barrier across all the workers (after each period).”
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD (2018, methodology): “…Federated Learning (McMahan et al., 2016), Elastic-Averaging (Zhang et al., 2015) and Decentralized averaging (Jiang et al., 2017; Lian et al., 2017), as well as synchronous/asynchronous distributed SGD with a central parameter server (Dean et al., 2012; Cui et al., 2014; Dutta et al., 2018).”
FreeLB: Enhanced Adversarial Training for Natural Language Understanding (2019, background): “Ebrahimi et al. (2018) propose a character/word replacement for crafting attacks, and show employing adversarial examples in training renders the models more robust.”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “Asynchronous stochastic optimization in shared-memory and distributed-memory systems has been extensively studied (Bertsekas and Tsitsiklis (1989) The idea of aggregating K asynchronous updates for convex objectives has been studied in (Dutta et al., 2018).”
Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD (2020, background): “However, in a wireless system where the computing nodes typically have low bandwidth and poor connectivity, the high communication delay and unpredictable nodes slowdown may greatly hinder the benefits of parallel computation [5, 6, 7, 8].”
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes (2018, unknown): “In data parallelism [67], different nodes store and train a different replica of the entire DNN on different pieces of data, and a central parameter server combines inputs from all the nodes to train a central replica of the DNN.”
Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization (2020, background): “However, our approach in comparison to Pan et al. (2017); Tandon et al. (2017); S. Dutta & Nagpurkar (2018) utilizes work completed by both fast and slow working nodes, thus results in faster wall time in convergence.”
SAFA: A Semi-Asynchronous Protocol for Fast Federated Learning With Low Overhead (2019, background): “[24] theoretically characterized the trade-off between reducing error (by including more stragglers) and shortening run time (by bounding staleness).”