Approximate Gradient Coding via Sparse Random Graphs

By Zachary B. Charles, Dimitris Papailiopoulos, Jordan S. Ellenberg. 2017

89 citations recorded by the source corpus.

Distributed algorithms are often beset by the straggler effect, where the slowest compute nodes in the system dictate the overall running time. Coding-theoretic techniques have been recently proposed to mitigate stragglers via algorithmic redundancy. Prior work in coded computation and gradient coding has mainly focused on exact recovery of the desired output. However, slightly inexact solutions can be acceptable in applications that are robust to noise, such as model training via gradient-based algorithms. In this work, we present computationally simple gradient codes based on sparse graphs that guarantee fast and approximately accurate distributed computation. We demonstrate that sacrificing a small amount of accuracy can significantly increase algorithmic robustness to stragglers.

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

Citations in the corpus

DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “, 2017), which uses codes to speed up synchronous distributed first-order methods (Raviv et al., 2017; Charles et al., 2017; Cotter et al., 2011).”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “Recent works have explored using codes to speed up distributed machine learning training [e.g., 20, 21, 63, 94, 109].”
Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks (2019, background): “The idea of random coding is popular in coding and information theory (see, for example, [20]) and has also been applied to computing distributed gradients [8], but random coding for tolerating Byzantines in the context of SignSGD is new and requires unique analysis.”
Coded Computing for Federated Learning at the Edge (2020, background): “Many other works on coded computing for straggler mitigation in distributed learning have been proposed recently (Ye & Abbe, 2018; Dhakal et al., 2019b; Yu et al., 2017; Raviv et al., 2017; Charles et al., 2017).”
Communication-Computation Efficient Gradient Coding (2018, background): “me time, the schemes in [11]–[13] are designed to combat stragglers for the worst-case scenario. While most research focused on recovering the exact results in the presence of stragglers, [13], [21], [22] suggested allowing some 3 small deviations from the exact gradient in each iteration of the gra”
Gradient Coding Using the Stochastic Block Model (2018, methodology): “They were later shown in [10] to be useful in the context of approximate gradient coding.”