# Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 17 Apr 2023.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Don't Decay the Learning Rate, Increase the Batch Size](https://mlsanity.com/paper/1711.00489/) (2017)
- [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)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [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)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [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)
- [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)
- [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)
- [Private Retrieval, Computing and Learning: Recent Progress and Future Challenges](https://mlsanity.com/paper/2108.00026/) (2021)
- [On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent](https://mlsanity.com/paper/2007.00534/) (2020)
- [Anytime Stochastic Gradient Descent: A Time to Hear from all the Workers](https://mlsanity.com/paper/1810.02976/) (2018)
- [Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers](https://mlsanity.com/paper/2002.11005/) (2020)
- [Coded Distributed Computing with Partial Recovery](https://mlsanity.com/paper/2007.02191/) (2020)
- [TOFEC: Achieving Optimal Throughput-Delay Trade-off of Cloud Storage Using Erasure Codes](https://mlsanity.com/paper/1307.8083/) (2013)
- [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)
- [Dynamic Heterogeneity-Aware Coded Cooperative Computation at the Edge](https://mlsanity.com/paper/1801.04357/) (2018)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Secure Private and Adaptive Matrix Multiplication Beyond the Singleton Bound](https://mlsanity.com/paper/2108.05742/) (2021)

## Abstract (arXiv)

In distributed machine learning, a central node outsources computationally expensive calculations to external worker nodes. The properties of optimization procedures like stochastic gradient descent (SGD) can be leveraged to mitigate the effect of unresponsive or slow workers called stragglers, that otherwise degrade the benefit of outsourcing the computation. This can be done by only waiting for a subset of the workers to finish their computation at each iteration of the algorithm. Previous works proposed to adapt the number of workers to wait for as the algorithm evolves to optimize the speed of convergence. In contrast, we model the communication and computation times using independent random variables. Considering this model, we construct a novel scheme that adapts both the number of workers and the computation load throughout the run-time of the algorithm. Consequently, we improve the convergence speed of distributed SGD while significantly reducing the computation load, at the expense of a slight increase in communication load.