Gradient descent (GD) methods are commonly employed in machine learning
problems to optimize the parameters of the model in an iterative fashion. For
problems with massive datasets, computations are distributed to many parallel
computing servers (i.e., workers) to speed up GD iterations. While distributed
computing can increase the computation speed significantly, the per-iteration
completion time is limited by the slowest straggling workers. Coded distributed
computing can mitigate straggling workers by introducing redundant
computations; however, existing coded computing schemes are mainly designed
against persistent stragglers, and partial computations at straggling workers
are discarded, leading to wasted computational capacity. In this paper, we
propose a novel gradient coding (GC) scheme which allows multiple coded
computations to be conveyed from each worker to the master per iteration. We
numerically show that the proposed GC with multi-message communication (MMC)
together with clustering provides significant improvements in the average
completion time (of each iteration), with minimal or no increase in the
communication load.

本文介绍了一种新的梯度编码（GC）方案，结合多消息通信（MMC）和聚类，以减少因服务器慢导致的迭代时间延长问题，其能有效提高平均完成时间并降低通信负荷。