CaltechAUTHORS
  A Caltech Library Service

Improving Distributed Gradient Descent Using Reed-Solomon Codes

Halbawi, Wael and Azizan, Navid and Salehi, Fariborz and Hassibi, Babak (2018) Improving Distributed Gradient Descent Using Reed-Solomon Codes. In: 2018 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 2027-2031. ISBN 978-1-5386-4780-6. http://resolver.caltech.edu/CaltechAUTHORS:20181126-142648719

[img] PDF - Submitted Version
See Usage Policy.

304Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20181126-142648719

Abstract

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2018.8437467DOIArticle
https://arxiv.org/abs/1706.05436arXivDiscussion Paper
ORCID:
AuthorORCID
Azizan, Navid0000-0002-4299-2963
Additional Information:© 2018 IEEE.
Record Number:CaltechAUTHORS:20181126-142648719
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20181126-142648719
Official Citation:W. Halbawi, N. Azizan, F. Salehi and B. Hassibi, "Improving Distributed Gradient Descent Using Reed-Solomon Codes," 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, 2018, pp. 2027-2031. doi: 10.1109/ISIT.2018.8437467
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:91186
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Nov 2018 22:31
Last Modified:02 Apr 2019 22:08

Repository Staff Only: item control page