# Gradient Coding from Cyclic MDS Codes and Expander Graphs

arXiv: https://arxiv.org/abs/1707.03858 · HTML: https://mlsanity.com/paper/1707.03858/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2017.

## Built on by (most cited first, 19 of 19)

- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [Soft BIBD and Product Gradient Codes](https://mlsanity.com/paper/2105.05231/) (2021)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Aspis: Robust Detection for Distributed Learning](https://mlsanity.com/paper/2108.02416/) (2021)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning](https://mlsanity.com/paper/2206.02450/) (2022)
- [Sequential Gradient Coding For Straggler Mitigation](https://mlsanity.com/paper/2211.13802/) (2022)
- [Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.08302/) (2022)
- [Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation](https://mlsanity.com/paper/2204.11168/) (2022)
- [Detection and Mitigation of Byzantine Attacks in Distributed Training](https://mlsanity.com/paper/2208.08085/) (2022)
- [Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load](https://mlsanity.com/paper/2304.08589/) (2023)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)
- [Successive Refinement in Large-Scale Computation: Advancing Model Inference Applications](https://mlsanity.com/paper/2402.07229/) (2024)
- [Design and Optimization of Hierarchical Gradient Coding for Distributed Learning at Edge Devices](https://mlsanity.com/paper/2406.10831/) (2024)
- [Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers](https://mlsanity.com/paper/2510.22539/) (2025)
- [Pipelined Gradient Coding](https://mlsanity.com/paper/2607.20739/) (2026)

## Abstract (arXiv)

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the ℓ2 error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.