# Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 45 references that are in the map.
- First posted on arXiv 4 Aug 2022.

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

- [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)
- [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)
- [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)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [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)
- [On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants](https://mlsanity.com/paper/1506.06840/) (2015)
- [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)
- [Accelerated Mini-Batch Stochastic Dual Coordinate Ascent](https://mlsanity.com/paper/1305.2581/) (2013)
- [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)
- [CYCLADES: Conflict-free Asynchronous Machine Learning](https://mlsanity.com/paper/1605.09721/) (2016)
- [Communication-Efficient Gradient Coding for Straggler Mitigation in Distributed Learning](https://mlsanity.com/paper/2005.07184/) (2020)

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

- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load](https://mlsanity.com/paper/2304.08589/) (2023)

## Abstract (arXiv)

We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on n workers, each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest k<n workers before updating the model, where k is a fixed parameter. The choice of the value of k presents a trade-off between the runtime (i.e., convergence rate) of SGD and the error of the model. Towards optimizing the error-runtime trade-off, we investigate distributed SGD with adaptive~k, i.e., varying k throughout the runtime of the algorithm. We first design an adaptive policy for varying k that optimizes this trade-off based on an upper bound on the error as a function of the wall-clock time that we derive. Then, we propose and implement an algorithm for adaptive distributed SGD that is based on a statistical heuristic. Our results show that the adaptive version of distributed SGD can reach lower error values in less time compared to non-adaptive implementations. Moreover, the results also show that the adaptive version is communication-efficient, where the amount of communication required between the master and the workers is less than that of non-adaptive versions.