# Approximate Gradient Coding with Optimal Decoding

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

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

- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)
- [Soft BIBD and Product Gradient Codes](https://mlsanity.com/paper/2105.05231/) (2021)
- [Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates](https://mlsanity.com/paper/2306.06559/) (2023)
- [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)
- [Gradient Coding in Decentralized Learning for Evading Stragglers](https://mlsanity.com/paper/2402.04193/) (2024)
- [Adaptive Coded Federated Learning: Privacy Preservation and Straggler Mitigation](https://mlsanity.com/paper/2403.14905/) (2024)
- [Nested Gradient Codes for Straggler Mitigation in Distributed Machine Learning](https://mlsanity.com/paper/2212.08580/) (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)
- [Approximate Gradient Coding for Privacy-Flexible Federated Learning with Non-IID Data](https://mlsanity.com/paper/2404.03524/) (2024)
- [Coded Robust Aggregation for Distributed Learning under Byzantine Attacks](https://mlsanity.com/paper/2506.01989/) (2025)
- [Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers](https://mlsanity.com/paper/2510.22539/) (2025)

## Abstract (arXiv)

In distributed optimization problems, a technique called gradient coding, which involves replicating data points, has been used to mitigate the effect of straggling machines. Recent work has studied approximate gradient coding, which concerns coding schemes where the replication factor of the data is too low to recover the full gradient exactly. Our work is motivated by the challenge of creating approximate gradient coding schemes that simultaneously work well in both the adversarial and stochastic models. To that end, we introduce novel approximate gradient codes based on expander graphs, in which each machine receives exactly two blocks of data points. We analyze the decoding error both in the random and adversarial straggler setting, when optimal decoding coefficients are used. We show that in the random setting, our schemes achieve an error to the gradient that decays exponentially in the replication factor. In the adversarial setting, the error is nearly a factor of two smaller than any existing code with similar performance in the random setting. We show convergence bounds both in the random and adversarial setting for gradient descent under standard assumptions using our codes. In the random setting, our convergence rate improves upon block-box bounds. In the adversarial setting, we show that gradient descent can converge down to a noise floor that scales linearly with the adversarial error to the gradient. We demonstrate empirically that our schemes achieve near-optimal error in the random setting and converge faster than algorithms which do not use the optimal decoding coefficients.