  Distributed implementations of gradient-based methods, wherein a server
distributes gradient computations across worker machines, need to overcome two
limitations: delays caused by slow running machines called 'stragglers', and
communication overheads. Recently, Ye and Abbe [ICML 2018] proposed a
coding-theoretic paradigm to characterize a fundamental trade-off between
computation load per worker, communication overhead per worker, and straggler
tolerance. However, their proposed coding schemes suffer from heavy decoding
complexity and poor numerical stability. In this paper, we develop a
communication-efficient gradient coding framework to overcome these drawbacks.
Our proposed framework enables using any linear code to design the encoding and
decoding functions. When a particular code is used in this framework, its
block-length determines the computation load, dimension determines the
communication overhead, and minimum distance determines the straggler
tolerance. The flexibility of choosing a code allows us to gracefully trade-off
the straggler threshold and communication overhead for smaller decoding
complexity and higher numerical stability. Further, we show that using a
maximum distance separable (MDS) code generated by a random Gaussian matrix in
our framework yields a gradient code that is optimal with respect to the
trade-off and, in addition, satisfies stronger guarantees on numerical
stability as compared to the previously proposed schemes. Finally, we evaluate
our proposed framework on Amazon EC2 and demonstrate that it reduces the
average iteration time by 16% as compared to prior gradient coding schemes.
