Approximate Gradient Coding With Optimal Decoding
Approximate Gradient Coding With Optimal Decoding
复制标题
DOI：
10.1109/jsait.2021.3100110
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Margalit Glasgow;Mary Wootters
中科院分区：
文献类型：
--
作者：
Margalit Glasgow;Mary Wootters
梯度代码使用数据复制来减轻散落机器在分布式机器学习中的影响。近似梯度代码考虑数据复制因子太低而无法准确恢复完整梯度的代码。我们的工作是由设计近似梯度代码的挑战所激发的，这些梯度代码同时在对抗和随机的散布模型中都可以很好地工作。我们基于扩展器图引入了新颖的近似梯度代码。当使用最佳解码系数时，我们分析了随机和对抗性散散的解码误差。使用随机的散落者，我们的代码会给梯度带来误差，该梯度在复制因子中呈指数衰减。使用对抗性散乱者，该错误小于在随机设置中具有相似性能的任何现有代码。在标准假设下，我们证明了两种编码梯度下降的两种设置中的收敛界限。使用随机的散落者，通过黑盒方法获得的速率，我们的收敛率提高了。使用对抗性的散落者，我们表明梯度下降会收敛到与对抗误差线性缩放到梯度的噪声层。我们从经验上证明，与不使用最佳解码系数的算法相比，我们的代码与随机的散乱者达到了近乎最佳的误差，并且收敛速度更快。
Gradient codes use data replication to mitigate the effect of straggling machines in distributed machine learning. Approximate gradient codes consider codes where the data replication factor is too low to recover the full gradient exactly. Our work is motivated by the challenge of designing approximate gradient codes that simultaneously work well in both the adversarial and random straggler models. We introduce novel approximate gradient codes based on expander graphs. We analyze the decoding error both for random and adversarial stragglers, when optimal decoding coefficients are used. With random stragglers, our codes achieve an error to the gradient that decays exponentially in the replication factor. With adversarial stragglers, the error is smaller than any existing code with similar performance in the random setting. We prove convergence bounds in both settings for coded gradient descent under standard assumptions. With random stragglers, our convergence rate improves upon rates obtained via black-box approaches. With adversarial stragglers, we show that gradient descent converges down to a noise floor that scales linearly with the adversarial error to the gradient. We demonstrate empirically that our codes achieve near-optimal error with random stragglers and converge faster than algorithms that do not use optimal decoding coefficients.