Gradient Coding from Cyclic MDS Codes and Expander Graphs
Abstract
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.
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.Attached Files
Published - raviv18a.pdf
Files
Name | Size | Download all |
---|---|---|
md5:ce1089c31c9fe8f164a44c6ce9e6d1bd
|
932.6 kB | Preview Download |
Additional details
- Eprint ID
- 101456
- Resolver ID
- CaltechAUTHORS:20200221-105223163
- CCF-1422549
- NSF
- CCF-1618689
- NSF
- DMS-1723052
- NSF
- W911NF-14-1-0258
- Army Research Office (ARO)
- Western Digital Corporation
- NVIDIA
- 1030/15
- Israel Science Foundation
- 2015814
- Binational Science Foundation (USA-Israel)
- Center for the Mathematics of Information, Caltech
- Lester-Deutsch Postdoctoral Fellowship
- Created
-
2020-02-21Created from EPrint's datestamp field
- Updated
-
2020-02-21Created from EPrint's last_modified field