Communication-Computation Efficient Gradient Coding

By Min Ye, Emmanuel Abbe. 2018

175 citations recorded by the source corpus.

This paper develops coding techniques to reduce the running time of distributed learning tasks. It characterizes the fundamental tradeoff to compute gradients (and more generally vector summations) in terms of three parameters: computation load, straggler tolerance and communication cost. It further gives an explicit coding scheme that achieves the optimal tradeoff based on recursive polynomial constructions, coding both across data subsets and vector components. As a result, the proposed scheme allows to minimize the running time for gradient computations. Implementations are made on Amazon EC2 clusters using Python with mpi4py package. Results show that the proposed scheme maintains the same generalization error while reducing the running time by $32\%$ compared to uncoded schemes and $23\%$ compared to prior coded schemes focusing only on stragglers (Tandon et al., ICML 2017).

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

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 Optimization & Training

Citations in the corpus

Scaling Neural Machine Translation (2018, background): “Another line of work explores strategies for improving communication efficiency in distributed synchronous training setting by abandoning “stragglers,” in particular by introducing redundancy in how the data is distributed across workers (Tandon et al., 2017; Ye and Abbe, 2018).”
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, methodology): “We implement LCC for regression on Amazon EC2 clusters, and empirically compare its performance with the conventional uncoded approaches, and two state-of-the-art straggler mitigation schemes: gradient coding (GC) [10], [14]–[16] and matrix-vector multiplication (MVM) based approaches [9], [11].”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “Following the conference publication [1], there have been several interesting works in the coded computing community (see [21] for survey) on coded linear algebra [22]–[37], coded convolutions [47], [48], gradient coding [38]–[42], coded Fast Fourier Transforms [55], [56], performance analysis [45],”
Communication-Efficient Edge AI: Algorithms and Systems (2020, background): “In [97], straggler tolerance and communication cost were considered jointly.”
Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air (2019, unknown): “The main goal is to recover gradient ∇F (θt) from computations executed by a limited number of workers, by jointly designing the distribution of the data samples across the workers, pre-processing of the computed gradients at the workers, and post-processing of the received computations by the PS [5”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, methodology): “Also in a very recent work [20], novel techniques have been developed to code across coordinates of the partial gradients, trading a larger recovery threshold for less amount of communication from each worker.”
Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks (2019, methodology): “2 Experiments on logistic regression models We trained a logistic regression model on the Amazon Employee Access data set from Kaggle3, which is used in [26, 30] on coded gradient computation schemes.”
Cross-Iteration Coded Computing (2018, background): “Some contemporary works on polynomial-encoded matrix operations include [31], [42], and also, notably [43], which focuses on matrix operations with reduced communication costs.”
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).”
1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed (2021, unknown): “Previous work has applied a range of techniques such as quantizaiton, sparsification, and sketching (Alistarh et al., 2017; Agarwal et al., 2018; Spring et al., 2019; Ye and Abbe, 2018; Shi et al., 2021).”
Gradient Coding From Cyclic MDS Codes and Expander Graphs (2017, background): “Furthermore, the exact setting was also discussed subsequent to this work in [28] and [29].”