# Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 26 Oct 2025.

## Builds on (most cited first, 11 of 11)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Communication-Computation Efficient Gradient Coding](https://mlsanity.com/paper/1802.03475/) (2018)
- [ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding](https://mlsanity.com/paper/1901.09671/) (2019)
- [Gradient Coding from Cyclic MDS Codes and Expander Graphs](https://mlsanity.com/paper/1707.03858/) (2017)
- [Fundamental Limits of Approximate Gradient Coding](https://mlsanity.com/paper/1901.08166/) (2019)
- [Approximate Gradient Coding with Optimal Decoding](https://mlsanity.com/paper/2006.09638/) (2020)
- [Coded Computation over Heterogeneous Clusters](https://mlsanity.com/paper/1701.05973/) (2017)
- [Approximate Gradient Coding via Sparse Random Graphs](https://mlsanity.com/paper/1711.06771/) (2017)
- [Timely Distributed Computation with Stragglers](https://mlsanity.com/paper/1910.03564/) (2019)
- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)

## Abstract (arXiv)

In this paper, we propose an optimally structured gradient coding scheme to mitigate the straggler problem in distributed learning. Conventional gradient coding methods often assume homogeneous straggler models or rely on excessive data replication, limiting performance in real-world heterogeneous systems. To address these limitations, we formulate an optimization problem minimizing residual error while ensuring unbiased gradient estimation by explicitly considering individual straggler probabilities. We derive closed-form solutions for optimal encoding and decoding coefficients via Lagrangian duality and convex optimization, and propose data allocation strategies that reduce both redundancy and computation load. We also analyze convergence behavior for λ-strongly convex and μ-smooth loss functions. Numerical results show that our approach significantly reduces the impact of stragglers and accelerates convergence compared to existing methods.