Title: Approximate Gradient Coding via Sparse Random Graphs,
Abstract: Distributed algorithms are often beset by the straggler effect, where the
slowest compute nodes in the system dictate the overall running time.
Coding-theoretic techniques have been recently proposed to mitigate stragglers
via algorithmic redundancy. Prior work in coded computation and gradient coding
has mainly focused on exact recovery of the desired output. However, slightly
inexact solutions can be acceptable in applications that are robust to noise,
such as model training via gradient-based algorithms. In this work, we present
computationally simple gradient codes based on sparse graphs that guarantee
fast and approximately accurate distributed computation. We demonstrate that
sacrificing a small amount of accuracy can significantly increase algorithmic
robustness to stragglers.