# Nested Gradient Codes for Straggler Mitigation in Distributed Machine Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 24 references that are in the map.
- First posted on arXiv 16 Dec 2022.

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

- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding](https://mlsanity.com/paper/1901.09671/) (2019)
- [Approximate Gradient Coding with Optimal Decoding](https://mlsanity.com/paper/2006.09638/) (2020)
- [Approximate Gradient Coding via Sparse Random Graphs](https://mlsanity.com/paper/1711.06771/) (2017)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [TOFEC: Achieving Optimal Throughput-Delay Trade-off of Cloud Storage Using Erasure Codes](https://mlsanity.com/paper/1307.8083/) (2013)
- [Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers](https://mlsanity.com/paper/1712.08230/) (2017)
- [Communication-Efficient Gradient Coding for Straggler Mitigation in Distributed Learning](https://mlsanity.com/paper/2005.07184/) (2020)
- [On Gradient Coding with Partial Recovery](https://mlsanity.com/paper/2102.10163/) (2021)
- [Soft BIBD and Product Gradient Codes](https://mlsanity.com/paper/2105.05231/) (2021)
- [Flexible Distributed Matrix Multiplication](https://mlsanity.com/paper/2107.10448/) (2021)

## Abstract (arXiv)

We consider distributed learning in the presence of slow and unresponsive worker nodes, referred to as stragglers. In order to mitigate the effect of stragglers, gradient coding redundantly assigns partial computations to the worker such that the overall result can be recovered from only the non-straggling workers. Gradient codes are designed to tolerate a fixed number of stragglers. Since the number of stragglers in practice is random and unknown a priori, tolerating a fixed number of stragglers can yield a sub-optimal computation load and can result in higher latency. We propose a gradient coding scheme that can tolerate a flexible number of stragglers by carefully concatenating gradient codes for different straggler tolerance. By proper task scheduling and small additional signaling, our scheme adapts the computation load of the workers to the actual number of stragglers. We analyze the latency of our proposed scheme and show that it has a significantly lower latency than gradient codes.