Speeding Up Distributed Machine Learning Using Codes

By Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, Kannan Ramchandran. 2015

924 citations recorded by the source corpus.

Codes are widely used in many engineering applications to offer <italic>robustness</italic> against <italic>noise</italic>. In large-scale systems, there are several types of noise that can affect the performance of distributed machine learning algorithms—straggler nodes, system failures, or communication bottlenecks—but there has been little interaction cutting across codes, machine learning, and distributed systems. In this paper, we provide theoretical insights on how <italic>coded</italic> solutions can achieve significant gains compared with uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: <italic>matrix multiplication</italic> and <italic>data shuffling</italic>. For matrix multiplication, we use codes to alleviate the effect of stragglers and show that if the number of homogeneous workers is <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>, and the runtime of each subtask has an exponential tail, coded computation can speed up distributed matrix multiplication by a factor of <inline-formula> <tex-math notation="LaTeX">$\log n$ </tex-math></inline-formula>. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage. We show that when a constant fraction <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> of the data matrix can be cached at each worker, and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the number of workers, <italic>coded shuffling</italic> reduces the communication cost by a factor of <inline-formula> <tex-math notation="LaTeX">$\left({\alpha + \frac {1}{n}}\right)\gamma (n)$ </tex-math></inline-formula> compared with uncoded shuffling, where <inline-formula> <tex-math notation="LaTeX">$\gamma (n)$ </tex-math></inline-formula> is the ratio of the cost of unicasting <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> messages to <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> users to multicasting a common message (of the same size) to <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> users. For instance, <inline-formula> <tex-math notation="LaTeX">$\gamma (n) \simeq n$ </tex-math></inline-formula> if multicasting a message to <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> users is as cheap as unicasting a message to one user. We also provide experimental results, corroborating our theoretical gains of the coded algorithms.

Subfields: Artificial Intelligence, Computer Networks and Communications, Efficiency & Compression, ML Systems & Hardware

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 Computer Networks and Communications

In Efficiency & Compression

In ML Systems & Hardware

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, methodology): “…decentralized optimization method with quantized messages was given in (Reisizadeh et al., 2018; Zhang et al., 2018), and more recently, new techniques have been developed in this context for convex problems (Doan et al., 2018; Koloskova et al., 2019; Berahas et al., 2019; Lee et al., 2018a,b).”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “There has been a significant recent interest in using codingtheoretic techniques to mitigate the well-known straggler problem [40], including gradient coding [43]–[46], encoding computation [33], [34], [47], and data encoding [41], [48].”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “, 2016), more recent work has employed coding theory to speed up distributed machine learning systems (Lee et al., 2017; Li et al., 2015; Dutta et al., 2016; 2017; Reisizadeh et al., 2017; Yang et al., 2017).”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “• In several prior works such as [19, 21, 42, 49], it is often assumed, for the ease of analysis, that runtimes are exponentially distributed.”
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].”
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, background): “As a by-product, we also prove the optimality of polynomial code under several other performance metrics considered in previous literature: computation latency [5, 10], probability of failure given a deadline [9], and communication load [16, 17, 18].”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, methodology): “We provide a technique (building on [2]–[5]) that introduces redundancy in the computation by designing a new error correction mechanism that allows the size of the individual dot products computed at each processing node to be shorter than the length of the input.”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “Additionally, use of coding in distributed computing has been explored in [13, 7].”
Fault Tolerance in Iterative-Convergent Machine Learning (2018, methodology): “Coded computing has been proposed as a technique to reduce the effects of stragglers and faults in distributed machine learning (Tandon et al., 2017; Karakus et al., 2017; Lee et al., 2018).”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, background): “On the other hand, in [16]–[19], error-correcting codes were applied to combat stragglers’ effect and speed up distributed linear algebra operations (e.”
Gradient Coding (2016, methodology): “The work of Lee et al. (2015) is the closest in spirit to our work, using coding theory and treating stragglers as erasures in the transmission of the computed results.”
Private Secure Coded Computation (2019, methodology): “In [1], for a matrix-vector multiplication, the matrix is (n, k)-MDS coded and distributed to n workers so that each encoded matrix is assigned to one worker.”
Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization (2020, background): “Recent papers on stragglers Lee et al. (2018); S. Dutta & Nagpurkar (2018) use the shifted exponential distribution to model T i ( t ) .”
On the optimal recovery threshold of coded matrix multiplication (2017, neutral): “expected time [1] and deadline exponents [24]).”