Communication-Computation Efficient Gradient Coding

Abstract

This paper develops coding techniques to reduce the running time of distributed learning tasks. It characterizes the fundamental tradeoff to compute gradients (and more generally vector summations) in terms of three parameters: computation load, straggler tolerance and communication cost. It further gives an explicit coding scheme that achieves the optimal tradeoff based on recursive polynomial constructions, coding both across data subsets and vector components. As a result, the proposed scheme allows to minimize the running time for gradient computations. Implementations are made on Amazon EC2 clusters using Python with mpi4py package. Results show that the proposed scheme maintains the same generalization error while reducing the running time by $32\%$ compared to uncoded schemes and $23\%$ compared to prior coded schemes focusing only on stragglers (Tandon et al., ICML 2017).

Cited by in corpus (22)

• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Joint Optimization of Communications and Federated Learning Over the Air
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• Computation Scheduling for Distributed Machine Learning with Straggling Workers
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• Straggler Mitigation with Tiered Gradient Codes
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• Coded Computing for Federated Learning at the Edge
• Coded Iterative Computing using Substitute Decoding
• Diversity/Parallelism Trade-off in Distributed Systems with Redundancy
• 1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Adaptive Gradient Coding
• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• Grand Challenges in Resilience: Autonomous System Resilience through Design and Runtime Measures
• Coded Elastic Computing
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Associative Convolutional Layers