Approximate Gradient Coding via Sparse Random Graphs
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Probabilistic Gradient Coding via Structure-Preserving Sparsification
Sparse Gaussian and Expansion-Preserving probabilistic gradient codes achieve BIBD-comparable worst-case robustness while extending feasible system parameters via sparsified random matrices.
-
Probabilistic Gradient Coding via Structure-Preserving Sparsification
SG and EP probabilistic gradient codes match BIBD-level worst-case performance while extending feasible system parameters through structure-preserving sparsification of random matrices.
-
Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching
Combines polynomial codes and randomized sketching into approximate distributed schemes that mitigate stragglers during optimization and machine learning tasks.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.