Title: Gradient Coding from Cyclic MDS Codes and Expander Graphs,
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.