# Soft BIBD and Product Gradient Codes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 11 May 2021.

## 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)
- [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)
- [Improving Distributed Gradient Descent Using Reed-Solomon Codes](https://mlsanity.com/paper/1706.05436/) (2017)
- [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)
- [Near-Optimal Straggler Mitigation for Distributed Gradient Methods](https://mlsanity.com/paper/1710.09990/) (2017)
- [Efficient Straggler Replication in Large-scale Parallel Computing](https://mlsanity.com/paper/1503.03128/) (2015)
- [Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers](https://mlsanity.com/paper/1904.13373/) (2019)
- [On Gradient Coding with Partial Recovery](https://mlsanity.com/paper/2102.10163/) (2021)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Gradient Coding via the Stochastic Block Model](https://mlsanity.com/paper/1805.10378/) (2018)

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

- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Nested Gradient Codes for Straggler Mitigation in Distributed Machine Learning](https://mlsanity.com/paper/2212.08580/) (2022)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)

## Abstract (arXiv)

Gradient coding is a coding theoretic framework to provide robustness against slow or unresponsive machines, known as stragglers, in distributed machine learning applications. Recently, Kadhe et al. proposed a gradient code based on a combinatorial design, called balanced incomplete block design (BIBD), which is shown to outperform many existing gradient codes in worst-case adversarial straggling scenarios. However, parameters for which such BIBD constructions exist are very limited. In this paper, we aim to overcome such limitations and construct gradient codes which exist for a wide range of system parameters while retaining the superior performance of BIBD gradient codes. Two such constructions are proposed, one based on a probabilistic construction that relax the stringent BIBD gradient code constraints, and the other based on taking the Kronecker product of existing gradient codes. The proposed gradient codes allow flexible choices of system parameters while retaining comparable error performance.