# Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Deep Speech 2: End-to-End Speech Recognition in English and Mandarin](https://mlsanity.com/paper/1512.02595/) (2015)
- [Don't Decay the Learning Rate, Increase the Batch Size](https://mlsanity.com/paper/1711.00489/) (2017)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Towards Flexible Device Participation in Federated Learning](https://mlsanity.com/paper/2006.06954/) (2020)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [Toward Understanding the Impact of Staleness in Distributed Machine Learning](https://mlsanity.com/paper/1810.03264/) (2018)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [Communication-Efficient Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2003.06307/) (2020)
- [Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions](https://mlsanity.com/paper/1606.02421/) (2016)
- [Hop: Heterogeneity-Aware Decentralized Training](https://mlsanity.com/paper/1902.01064/) (2019)
- [Dynamic backup workers for parallel machine learning](https://mlsanity.com/paper/2004.14696/) (2020)

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

- [MimiC: Combating Client Dropouts in Federated Learning by Mimicking Central Updates](https://mlsanity.com/paper/2306.12212/) (2023)
- [Critical Learning Periods in Federated Learning](https://mlsanity.com/paper/2109.05613/) (2021)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)

## Abstract (arXiv)

With the increasing demand for large-scale training of machine learning models, consensus-based distributed optimization methods have recently been advocated as alternatives to the popular parameter server framework. In this paradigm, each worker maintains a local estimate of the optimal parameter vector, and iteratively updates it by waiting and averaging all estimates obtained from its neighbors, and then corrects it on the basis of its local dataset. However, the synchronization phase can be time consuming due to the need to wait for textitstragglers, i.e., slower workers. An efficient way to mitigate this effect is to let each worker wait only for updates from the fastest neighbors before updating its local parameter. The remaining neighbors are called textitbackup workers. To minimize the globally training time over the network, we propose a fully distributed algorithm to dynamically determine the number of backup workers for each worker. We show that our algorithm achieves a linear speedup for convergence (i.e., convergence performance increases linearly with respect to the number of workers). We conduct extensive experiments on MNIST and CIFAR-10 to verify our theoretical results.