# Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 31 Jan 2022.

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

- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [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)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Communication-Computation Efficient Gradient Coding](https://mlsanity.com/paper/1802.03475/) (2018)
- [Gradient Coding from Cyclic MDS Codes and Expander Graphs](https://mlsanity.com/paper/1707.03858/) (2017)
- [Straggler-aware Distributed Learning: Communication Computation Latency Trade-off](https://mlsanity.com/paper/2004.04948/) (2020)
- [Improving Distributed Gradient Descent Using Reed-Solomon Codes](https://mlsanity.com/paper/1706.05436/) (2017)
- [Robust and Communication-Efficient Collaborative Learning](https://mlsanity.com/paper/1907.10595/) (2019)
- [Gradient Coding with Clustering and Multi-message Communication](https://mlsanity.com/paper/1903.01974/) (2019)
- [LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1905.09148/) (2019)
- [Anytime MiniBatch: Exploiting Stragglers in Online Distributed Optimization](https://mlsanity.com/paper/2006.05752/) (2020)
- [A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication](https://mlsanity.com/paper/1811.10751/) (2018)
- [Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning](https://mlsanity.com/paper/1803.05397/) (2018)
- [Anytime Stochastic Gradient Descent: A Time to Hear from all the Workers](https://mlsanity.com/paper/1810.02976/) (2018)
- [Speeding Up Distributed Gradient Descent by Utilizing Non-persistent Stragglers](https://mlsanity.com/paper/1808.02240/) (2018)
- [Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation](https://mlsanity.com/paper/1806.01259/) (2018)
- [Distributed Gradient Descent with Coded Partial Gradient Computations](https://mlsanity.com/paper/1811.09271/) (2018)
- [Parity Models: A General Framework for Coding-Based Resilience in ML Inference](https://mlsanity.com/paper/1905.00863/) (2019)
- [Coded Sparse Matrix Multiplication](https://mlsanity.com/paper/1802.03430/) (2018)
- [Distributed Matrix-Vector Multiplication: A Convolutional Coding Approach](https://mlsanity.com/paper/1901.08716/) (2019)
- [Slow and Stale Gradients Can Win the Race](https://mlsanity.com/paper/2003.10579/) (2020)
- [Gradient Coding](https://mlsanity.com/paper/1612.03301/) (2016)

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

- [Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors](https://mlsanity.com/paper/2202.03469/) (2022)

## Abstract (arXiv)

Coded distributed computation has become common practice for performing gradient descent on large datasets to mitigate stragglers and other faults. This paper proposes a novel algorithm that encodes the partial derivatives themselves and furthermore optimizes the codes by performing lossy compression on the derivative codewords by maximizing the information contained in the codewords while minimizing the information between the codewords. The utility of this application of coding theory is a geometrical consequence of the observed fact in optimization research that noise is tolerable, sometimes even helpful, in gradient descent based learning algorithms since it helps avoid overfitting and local minima. This stands in contrast with much current conventional work on distributed coded computation which focuses on recovering all of the data from the workers. A second further contribution is that the low-weight nature of the coding scheme allows for asynchronous gradient updates since the code can be iteratively decoded; i.e., a worker's task can immediately be updated into the larger gradient. The directional derivative is always a linear function of the direction vectors; thus, our framework is robust since it can apply linear coding techniques to general machine learning frameworks such as deep neural networks.