LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning

Abstract

Gradient-based distributed learning in Parameter Server (PS) computing architectures is subject to random delays due to straggling worker nodes, as well as to possible communication bottlenecks between PS and workers. Solutions have been recently proposed to separately address these impairments based on the ideas of gradient coding, worker grouping, and adaptive worker selection. This paper provides a unified analysis of these techniques in terms of wall-clock time, communication, and computation complexity measures. Furthermore, in order to combine the benefits of gradient coding and grouping in terms of robustness to stragglers with the communication and computation load gains of adaptive selection, novel strategies, named Lazily Aggregated Gradient Coding (LAGC) and Grouped-LAG (G-LAG), are introduced. Analysis and results show that G-LAG provides the best wall-clock time and communication performance, while maintaining a low computational cost, for two representative distributions of the computing times of the worker nodes.

arXiv commentSubmitted

References in corpus (12)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Speeding Up Distributed Machine Learning Using Codes
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Distributed Mean Estimation with Limited Communication
• Communication-Computation Efficient Gradient Coding
• Communication-Efficient Distributed Dual Coordinate Ascent
• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy