# ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2019.

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

- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [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)
- [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)
- [STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization](https://mlsanity.com/paper/2210.03521/) (2022)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [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)
- [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)
- [Adaptive Worker Grouping For Communication-Efficient and Straggler-Tolerant Distributed SGD](https://mlsanity.com/paper/2201.04301/) (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)
- [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)
- [NeRCC: Nested-Regression Coded Computing for Resilient Distributed Prediction Serving Systems](https://mlsanity.com/paper/2402.04377/) (2024)
- [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)
- [Pipelined Gradient Coding](https://mlsanity.com/paper/2607.20739/) (2026)

## Abstract (arXiv)

We present ErasureHead, a new approach for distributed gradient descent (GD) that mitigates system delays by employing approximate gradient coding. Gradient coded distributed GD uses redundancy to exactly recover the gradient at each iteration from a subset of compute nodes. ErasureHead instead uses approximate gradient codes to recover an inexact gradient at each iteration, but with higher delay tolerance. Unlike prior work on gradient coding, we provide a performance analysis that combines both delay and convergence guarantees. We establish that down to a small noise floor, ErasureHead converges as quickly as distributed GD and has faster overall runtime under a probabilistic delay model. We conduct extensive experiments on real world datasets and distributed clusters and demonstrate that our method can lead to significant speedups over both standard and gradient coded GD.