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.

References in corpus (1)

• Adding Gradient Noise Improves Learning for Very Deep Networks

Cited by in corpus (14)

• Communication-Computation Efficient Secure Aggregation for Federated Learning
• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• Robust Gradient Descent via Moment Encoding with LDPC Codes
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• A Survey of Coded Distributed Computing
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• Gradient Coding via the Stochastic Block Model
• Coded Computing for Federated Learning at the Edge
• A locality-based approach for coded computation
• Coded Iterative Computing using Substitute Decoding
• A Survey on Fault-tolerance in Distributed Optimization and Machine Learning
• Heterogeneity-aware Gradient Coding for Straggler Tolerance
• Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data