Improving Distributed Gradient Descent Using Reed-Solomon Codes

By Wael Halbawi, Navid Azizan, Fariborz Salehi, Babak Hassibi. 2017

166 citations recorded by the source corpus.

Today's massively-sized datasets have made it necessary to often perform computations on them in a distributed manner. In principle, a computational task is divided into subtasks which are distributed over a cluster operated by a taskmaster. One issue faced in practice is the delay incurred due to the presence of slow machines, known as stragglers. Several schemes, including those based on replication, have been proposed in the literature to mitigate the effects of stragglers and more recently, those inspired by coding theory have begun to gain traction. In this work, we consider a distributed gradient descent setting suitable for a wide class of machine learning problems. We adopt the framework of Tandon et al. [1] and present a deterministic scheme that, for a prescribed per-machine computational effort, recovers the gradient from the least number of machines $f$ theoretically permissible, via an $O(f^{2})$ decoding algorithm. The idea is based on a suitably designed Reed-Solomon code that has a sparsest and balanced generator matrix. We also provide a theoretical delay model which can be used to minimize the expected waiting time per computation by optimally choosing the parameters of the scheme. Finally, we supplement our theoretical findings with numerical results that demonstrate the efficacy of the method and its advantages over competing schemes.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

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

In Computational Theory and Mathematics

Citations in the corpus

“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “In fact, the problem of gradient coding [38]–[41] is deeply connected with our problem when M = 1, P = N , and A is simply the vector [1, 1, .”
Data Encoding for Byzantine-Resilient Distributed Gradient Descent (2018, methodology): “There has been significant recent interest in using codingtheoretic techniques to mitigate the well-known straggler problem [12], including gradient coding [15]–[18], encoding computation [19], [20], data encoding [13].”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, background): “There are also works dealing with coded gradient descent [24, 43, 56], coded convolution [15], coded Fourier Transform [64], Page Rank [62], and coded distributed optimization [36] – in general any distributed linear computation can essentially be expressed as a matrix multiplication/addition operat”
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].”
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].”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, methodology): “Furthermore, in [8] and [9], the same performance was achieved using deterministic constructions of Reed-Solomon (RS) codes and cyclic MDS (CM) codes.”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, methodology): “, quadratic in (n− r) when partial gradients are encoded using Reed-Solomon codes [17].”
Data Encoding Methods 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 [12], including gradient coding [15]–[18], encoding computation [19], [20], data encoding [13].”
Communication-Computation Efficient Gradient Coding (2018, background): “ can be up to 80%, and when n= 26, our algorithm crushes. Note that numerical instability of our coding scheme is NOT due to the introduction of the communication cost reduction factor m. In fact, in [12], [13] the authors presented coding schemes to achieve (5) for the special case of m= 1, and the”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, background): “A more recent line of work that address the straggler problem is based on coding-theoryinspired techniques Tandon et al. (2017); Lee et al. (2016); Dutta et al. (2016); Karakus et al. (2017a,b); Yang et al. (2017); Halbawi et al. (2017); Reisizadeh et al. (2017).”
Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “Using Reed-Solomon codes, Halbawi et al. [96] made the learning system more robust to stragglers compared with [93].”