Gradient Coding with Clustering and Multi-message Communication
  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.
