On Gradient Coding With Partial Recovery
- 19 December 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 71 (2) , 644-657
Abstract
We consider a generalization of the gradient coding framework where a dataset is divided across n workers and each worker transmits to a master node one or more linear combinations of the gradients over its assigned data subsets. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of straggler workers, we relax the goal to computing the sum of at least some α fraction of the gradients. We begin by deriving a lower bound on the computation load of any scheme and also propose two strategies which achieve this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in n . We then propose schemes based on cyclic assignment which utilize n data partitions and have a lower communication load. When each worker transmits a single linear combination, we prove lower bounds on the computation load of any scheme using n data partitions. Finally, we describe a class of schemes which achieve different intermediate operating points for the computation and communication load and provide simulation results to demonstrate the empirical performance of our schemes.Keywords
This publication has 22 references indexed in Scilit:
- “Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot ProductsIEEE Transactions on Information Theory, 2019
- Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers2019
- Speeding Up Distributed Gradient Descent by Utilizing Non-persistent Stragglers2019
- Robust Gradient Descent via Moment Encoding and LDPC Codes2019
- Distributed Gradient Descent with Coded Partial Gradient Computations2019
- Improving Distributed Gradient Descent Using Reed-Solomon Codes2018
- A Fundamental Tradeoff Between Computation and Communication in Distributed ComputingIEEE Transactions on Information Theory, 2017
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- Coded convolution for parallel and distributed computing within a deadline2017
- Large-Scale Machine Learning with Stochastic Gradient Descent2010