Gradient Coding

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

78 citations recorded by the source corpus.

We propose a novel coding theoretic framework for mitigating stragglers in distributed learning. We show how carefully replicating data blocks and coding across gradients can provide tolerance to failures and stragglers for Synchronous Gradient Descent. We implement our schemes in python (using MPI) to run on Amazon EC2, and show how we compare against baseline approaches in running time and generalization error.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

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

In Computer Vision and Pattern Recognition

Citations in the corpus

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, methodology): “Many methods have been proposed to address systems heterogeneity and in particular stragglers in distributed learning using coding theory, e.g., [Dutta et al., 2016, Lee et al., 2018, Reisizadeh et al., 2019b, Tandon et al., 2016, Yu et al., 2017].”
Robust and Communication-Efficient Collaborative Learning (2019, background): “Another line of work proposed using coding theoretic ideas for speeding up distributed machine learning (Lee et al., 2018c; Tandon et al., 2016; Yu et al., 2017; Reisizadeh et al., 2019b,c), but they work mostly for master-worker setup and particular computation types such as linear computations or…”
Speeding Up Distributed Machine Learning Using Codes (2015, methodology): “By applying Gradient Coding to this algorithm, one can achieve straggler tolerance but at the cost of significant computation and storage overheads.”
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, positive): “However, there have been recent results demonstrating that coding can play a transformational role for creating and exploiting computation redundancy to effectively alleviate the impact of stragglers [5, 6, 7, 8, 9].”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “Machine Learning Training and Gradient Coding: One typical scenario that arises in machine learning training, as also pointed out in [38], is when A is fixed and known in advance and is required to be multiplied with another vector or matrix that is generated in real-time.”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “[21] considers a gradient descent method on an architecture where each data sample is replicated across nodes, and designs a code such that the exact gradient can be recovered as long as fewer than a certain number of nodes fail.”
Gradient Coding From Cyclic MDS Codes and Expander Graphs (2017, methodology): “To the best of the authors’ knowledge, the gradient coding framework was defined in [20], which established the fundamental bound d ≥ s + 1, and provided two schemes which attain it.”
Gradient Coding Using the Stochastic Block Model (2018, methodology): “We are particularly interested in the setting where the number of stragglers is a constant fraction of k, as this is when previous theory such as that in [8] breaks down.”
Minimizing latency for secure distributed computing (2017, background): “[15] introduced a gradient coding framework for straggler mitigation for distributed gradient descent algorithms.”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, methodology): “In the cyclic repetition scheme, each worker sends the master a linear combination of the computed partial gradients, whose coefficients are specified by the coding scheme in [7].”
Encoded distributed optimization (2017, background): “For instance, for e node failures, the results in [4] imply that one needs a redundancy factor of e+1 for exact recovery, whereas we show that the solution can be reasonably approximated with a redundancy factor of 2.”
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].”
Improving Distributed Gradient Descent Using Reed-Solomon Codes (2017, methodology): “[1], which aims at mitigating the 2018 IEEE International Symposium on Information Theory (ISIT)”
Approximate Gradient Coding via Sparse Random Graphs (2017, methodology): “The ﬁrst is the Fractional Repetition Code (FRC) proposed in [23].”
Secure Distributed Computing With Straggling Servers Using Polynomial Codes (2019, methodology): “Furthermore, coding techniques may be exploited to mitigate the straggling effect for various distributed computing scenarios such as distributed matrix multiplication [3]–[8], distributed convolution [9], and distributed gradient descent [10], [11].”
Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes (2018, background): “[36] introduced a framework called gradient coding for straggler mitigation in distributed gradient-descent based algorithms.”