Communication-Efficient Gradient Coding for Straggler Mitigation in\n Distributed Learning

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