Gradient Coding: Avoiding Stragglers in Distributed Learning

By Rashish Tandon, Qi Lei, A. Dimakis, Nikos Karampatziakis. 2017

541 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Scaling Neural Machine Translation (2018, background): “Another line of work explores strategies for improving communication efﬁciency in distributed synchronous training setting by abandoning “stragglers,” in particular by introducing redundancy in how the data is distributed across workers (Tandon et al., 2017; Ye and Abbe, 2018).”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “There has been signiﬁcant recent interest in using coding-theoretic techniques to mitigate the well-known straggler problem [DB13], including gradient coding [TLDK17, RTDT18, CP18, HRSH18], encoding computation [LLP + 18, DCG16], data encoding [KSDY17].”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, methodology): “In contrast to previous work on stragglers and gradient codes (Tandon et al., 2017; Raviv et al., 2017; Charles et al., 2017), our decoders are tailored to the adversarial setting and use different methods.”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “Recent works such as [Tandon et al., 2017] propose erasure coding techniques to overcome straggling learners.”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “cy. Recent works have explored using codes to speed up distributed machine learning training [e.g., 20, 21, 63, 94, 109]. For instance, in the presence of stragglers, gradient coding and its variants [20, 21, 109] carefully replicate data blocks (as well as the gradient computation on those data blo”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “For M > 1, a straightforward extension of the gradient coding strategy proposed in [38], [39] would encode each row of A separately and require M dot products, each of length N(P−K+1) P , at each processing node.”
Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air (2019, background): “While coded computation [5] and gradient coding [6] approaches allow mitigating persistent stragglers, they cannot exploit partial computations executed by non-persistent stragglers.”
One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysis (2020, background): “The first is to discard the updates from slow-responding edge devices (stragglers) for fast update synchronization [8], [9].”
Distributed Learning in Wireless Networks: Recent Progress and Future Challenges (2021, background): “Researchers have attempted to reduce the resultant communication latency using different approaches such as excluding slow devices (“stragglers") [92], [93], selecting only those devices whose updates can significantly”
Cross-Iteration Coded Computing (2018, methodology): “For coding iterative algorithms, almost all existing work focuses on the optimization of a single iteration or weighted averaging in a single communication round [24]–[34].”
Coded Computing for Federated Learning at the Edge (2020, methodology): “Related Works: Coded computing is a new paradigm that has been developed for injecting computation redundancy in unorthodox encoded forms to efficiently deal with communication bottleneck and system disturbances like stragglers, outages, node failures, and adversarial computations in distributed sys”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, methodology): “We provide a sample result from our experiments in Table Ib TABLE I: Performance comparison between Gradient Coding (GC) schemes [16]–[18], [20] and the proposed Polynomially Coded Regression (PCR) for running distributed least-squares regression on a system consisting of n workers and a training…”
Communication-Computation Efficient Gradient Coding (2018, background): “, 2016) and (Tandon et al., 2017; Halbawi et al., 2017; Raviv et al., 2017) do not have the recursive polynomial structure, which is the main technical novelty in our paper.”
High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning (2020, background): “To tackle this challenge, numerous schemes have been developed for compressing stochastic gradients to reduce the said communication overhead [6], [7].”
Coded Computation Over Heterogeneous Clusters (2019, background): “The work in [16] proposes coding schemes for mitigating stragglers in distributed batch gradient computation.”
Broadband Analog Aggregation for Low-Latency Federated Edge Learning (2018, methodology): “Later, the design was enhanced by coding the updates such that the full updateaveraging can be still realized using only a portion of coded updates [9].”
Coded computation over heterogeneous clusters (2017, background): “The work in [16] proposes coding schemes for mitigating stragglers in distributed batch gradient computation.”