# Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 63 references that are in the map.
- First posted on arXiv 16 Feb 2022.

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

- [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)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [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)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity](https://mlsanity.com/paper/2012.14453/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Communication-Computation Efficient Gradient Coding](https://mlsanity.com/paper/1802.03475/) (2018)
- [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)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Straggler-aware Distributed Learning: Communication Computation Latency Trade-off](https://mlsanity.com/paper/2004.04948/) (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)
- [On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent](https://mlsanity.com/paper/2007.00534/) (2020)
- [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)
- [Distributed Gradient Descent with Coded Partial Gradient Computations](https://mlsanity.com/paper/1811.09271/) (2018)
- [Computation Scheduling for Distributed Machine Learning with Straggling Workers](https://mlsanity.com/paper/1810.09992/) (2018)
- [Distributed Storage Allocations for Optimal Service Rates](https://mlsanity.com/paper/2102.04322/) (2021)

## Abstract (arXiv)

We consider the distributed SGD problem, where a main node distributes gradient calculations among n workers. By assigning tasks to all the workers and waiting only for the k fastest ones, the main node can trade-off the algorithm's error with its runtime by gradually increasing k as the algorithm evolves. However, this strategy, referred to as adaptive k-sync, neglects the cost of unused computations and of communicating models to workers that reveal a straggling behavior. We propose a cost-efficient scheme that assigns tasks only to k workers, and gradually increases k. We introduce the use of a combinatorial multi-armed bandit model to learn which workers are the fastest while assigning gradient calculations. Assuming workers with exponentially distributed response times parameterized by different means, we give empirical and theoretical guarantees on the regret of our strategy, i.e., the extra time spent to learn the mean response times of the workers. Furthermore, we propose and analyze a strategy applicable to a large class of response time distributions. Compared to adaptive k-sync, our scheme achieves significantly lower errors with the same computational efforts and less downlink communication while being inferior in terms of speed.