A Caltech Library Service

Gradient Coding from Cyclic MDS Codes and Expander Graphs

Raviv, Netanel and Tamo, Itzhak and Tandon, Rashish and Dimakis, Alexandros G. (2018) Gradient Coding from Cyclic MDS Codes and Expander Graphs. Proceedings of Machine Learning Research, 80 . pp. 4305-4313. ISSN 1938-7228.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favourably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the ℓ₂ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that the normalized adjacency matrix of an expander graph can yield excellent approximate gradient codes, and that this approach allows us to perform significantly less computation compared to exact gradient coding. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

Item Type:Article
Related URLs:
URLURL TypeDescription
Raviv, Netanel0000-0002-1686-1994
Additional Information:© 2018 by the author(s). This research has been supported by NSF Grants CCF 1422549, 1618689, DMS 1723052, ARO YIP W911NF-14-1-0258 and research gifts by Google, Western Digital and NVIDIA. The work of Rashish Tandon was done while he was at UT Austin, prior to joining apple. The work of Itzhak Tamo and Netanel Raviv was supported in part ISF Grant 1030/15 and NSF-BSF Grant 2015814. The work of Netanel Raviv was supported in part by the postdoctoral fellowship of the Center for the Mathematics of Information (CMI), Caltech, and in part by the Lester-Deutsch postdoctoral fellowship.
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-14-1-0258
Western Digital CorporationUNSPECIFIED
Israel Science Foundation1030/15
Binational Science Foundation (USA-Israel)2015814
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch Postdoctoral FellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20200221-105223163
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101456
Deposited By: Tony Diaz
Deposited On:21 Feb 2020 20:33
Last Modified:21 Feb 2020 20:33

Repository Staff Only: item control page