Robust Gradient Descent via Moment Encoding with LDPC Codes
  This paper considers the problem of implementing large-scale gradient descent
algorithms in a distributed computing setting in the presence of {\em
straggling} processors. To mitigate the effect of the stragglers, it has been
previously proposed to encode the data with an erasure-correcting code and
decode at the master server at the end of the computation. We, instead, propose
to encode the second-moment of the data with a low density parity-check (LDPC)
code. The iterative decoding algorithms for LDPC codes have very low
computational overhead and the number of decoding iterations can be made to
automatically adjust with the number of stragglers in the system. We show that
for a random model for stragglers, the proposed moment encoding based gradient
descent method can be viewed as the stochastic gradient descent method. This
allows us to obtain convergence guarantees for the proposed solution.
Furthermore, the proposed moment encoding based method is shown to outperform
the existing schemes in a real distributed computing setup.
