Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits.
Journal:
Entropy (Basel, Switzerland)
Published Date:
May 20, 2025
Abstract
We consider the distributed stochastic gradient descent problem, where a main node distributes gradient calculations among workers. By assigning tasks to all workers and waiting only for the fastest ones, the main node can trade off the algorithm's error with its runtime by gradually increasing as the algorithm evolves. However, this strategy, referred to as , 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 workers, and gradually increases . To learn which workers are the fastest while assigning gradient calculations, we introduce the use of a combinatorial multi-armed bandit model. Assuming workers have exponentially distributed response times with different means, we provide both empirical and theoretical guarantees on the regret of our strategy, i.e., the extra time spent learning the mean response times of the workers. Furthermore, we propose and analyze a strategy that is applicable to a large class of response time distributions. Compared to adaptive -sync, our scheme achieves significantly lower errors with the same computational efforts and less downlink communication while being inferior in terms of speed.
Authors
Keywords
No keywords available for this article.
