Gradient Coding From Cyclic MDS Codes and Expander Graphs
Gradient Coding From Cyclic MDS Codes and Expander Graphs
复制标题
DOI：
10.1109/tit.2020.3029396
复制
发表时间：
2017-07
影响因子：
2.5
通讯作者：
Netanel Raviv;Itzhak Tamo;Rashish Tandon;A. Dimakis
中科院分区：
文献类型：
--
作者：
Netanel Raviv;Itzhak Tamo;Rashish Tandon;A. Dimakis
梯度编码是分布式学习中的一种落后者缓解技术。在本文中，我们设计了新的梯度码使用工具，从经典的编码理论，即循环MDS码，这与现有的解决方案相比毫不逊色，无论是在适用的参数范围和所涉及的算法的复杂性。其次，我们介绍了梯度编码问题的一个近似变体，其中我们解决近似梯度计算，而不是精确的。这种方法能够实现适度降级，即，近似梯度的$\ell _{2}$误差是离散者数目的递减函数。我们的主要结果是，规范化的邻接矩阵的扩展图产生优秀的近似梯度代码，这使得显着更少的计算相比，精确的梯度编码，并保证更快的收敛速度比平凡的解决方案在标准假设下。我们在Amazon EC2上对我们的方法进行了实验测试，结果表明近似梯度编码的泛化误差非常接近完整梯度，同时需要的计算量明显减少。
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 favorably 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 normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. 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.