Gradient Coding from Cyclic MDS Codes and Expander Graphs

Netanel Raviv, Rashish Tandon, Alex Dimakis, Itzhak Tamo
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4305-4313, 2018.

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 $\ell_2$ 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-raviv18a, title = {Gradient Coding from Cyclic {MDS} Codes and Expander Graphs}, author = {Raviv, Netanel and Tandon, Rashish and Dimakis, Alex and Tamo, Itzhak}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4305--4313}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/raviv18a/raviv18a.pdf}, url = {https://proceedings.mlr.press/v80/raviv18a.html}, 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 $\ell_2$ 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.} }
Endnote
%0 Conference Paper %T Gradient Coding from Cyclic MDS Codes and Expander Graphs %A Netanel Raviv %A Rashish Tandon %A Alex Dimakis %A Itzhak Tamo %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-raviv18a %I PMLR %P 4305--4313 %U https://proceedings.mlr.press/v80/raviv18a.html %V 80 %X 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 $\ell_2$ 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.
APA
Raviv, N., Tandon, R., Dimakis, A. & Tamo, I.. (2018). Gradient Coding from Cyclic MDS Codes and Expander Graphs. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4305-4313 Available from https://proceedings.mlr.press/v80/raviv18a.html.

Related Material