Approximate Gradient Coding with Optimal Decoding
  In distributed optimization problems, a technique called gradient coding,
which involves replicating data points, has been used to mitigate the effect of
straggling machines. Recent work has studied approximate gradient coding, which
concerns coding schemes where the replication factor of the data is too low to
recover the full gradient exactly. Our work is motivated by the challenge of
creating approximate gradient coding schemes that simultaneously work well in
both the adversarial and stochastic models. To that end, we introduce novel
approximate gradient codes based on expander graphs, in which each machine
receives exactly two blocks of data points. We analyze the decoding error both
in the random and adversarial straggler setting, when optimal decoding
coefficients are used. We show that in the random setting, our schemes achieve
an error to the gradient that decays exponentially in the replication factor.
In the adversarial setting, the error is nearly a factor of two smaller than
any existing code with similar performance in the random setting. We show
convergence bounds both in the random and adversarial setting for gradient
descent under standard assumptions using our codes. In the random setting, our
convergence rate improves upon block-box bounds. In the adversarial setting, we
show that gradient descent can converge down to a noise floor that scales
linearly with the adversarial error to the gradient. We demonstrate empirically
that our schemes achieve near-optimal error in the random setting and converge
faster than algorithms which do not use the optimal decoding coefficients.
