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.

Cited by in corpus (5)

• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• A Survey of Coded Distributed Computing
• A locality-based approach for coded computation
• A Survey on Fault-tolerance in Distributed Optimization and Machine Learning
• Heterogeneity-aware Gradient Coding for Straggler Tolerance