Gradient Coding From Cyclic MDS Codes and Expander Graphs

By Netanel Raviv, Itzhak Tamo, Rashish Tandon, A. Dimakis. 2017

199 citations recorded by the source corpus.

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell _{2}$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

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, methodology): “In contrast to previous work on stragglers and gradient codes [TLDK17, RTTD17, CPE17], our decoders are tailored to the adversarial setting and use different methods.”
Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “Raviv et al. [95] adopted tools from classic coding theory, i.e., cyclic MDS codes, to achieve favorable performance of gradient coding in terms of the applicable range of parameters and in the complexity of the coding algorithms.”
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes (2018, methodology): “Coding for data parallel training is examined in [24], [25], [29], [43].”
Communication-Computation Efficient Gradient Coding (2018, methodology): “deﬁne these polynomials by specifying their roots so that the two properties of Bare satisﬁed. We also mention that the conditions in our construction are more restrictive than those in [14] and [11]–[13]: In our setting, the conditions in [14] only require that the last mcolumns of Bcontain at most”
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).”
Improving Distributed Gradient Descent Using Reed-Solomon Codes (2017, methodology): “The recent work [11] includes a coding scheme that is similar to the one presented here.”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, methodology): “Recently a few interesting papers [7]–[9] utilize coding theory to mitigate the effect of stragglers in distributed GD.”
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…”
Gradient Coding Using the Stochastic Block Model (2018, methodology): “Gradient coding, a straggler-mitigating technique for distributed gradient-based methods, was first proposed in [8] and was later extended in [9].”