  We present ErasureHead, a new approach for distributed gradient descent (GD)
that mitigates system delays by employing approximate gradient coding. Gradient
coded distributed GD uses redundancy to exactly recover the gradient at each
iteration from a subset of compute nodes. ErasureHead instead uses approximate
gradient codes to recover an inexact gradient at each iteration, but with
higher delay tolerance. Unlike prior work on gradient coding, we provide a
performance analysis that combines both delay and convergence guarantees. We
establish that down to a small noise floor, ErasureHead converges as quickly as
distributed GD and has faster overall runtime under a probabilistic delay
model. We conduct extensive experiments on real world datasets and distributed
clusters and demonstrate that our method can lead to significant speedups over
both standard and gradient coded GD.
