Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits

We consider the distributed stochastic gradient descent problem, where a main node distributes gradient calculations among <i>n</i> workers. By assigning tasks to all workers and waiting only for the <i>k</i> fastest ones, the main node can trade off the algorithm's error with its runtime by gradually increasing <i>k</i> as the algorithm evolves. However, this strategy, referred to as <i>adaptive k-sync</i>, 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 <i>k</i> workers, and gradually increases <i>k</i>. 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 <i>k</i>-sync, our scheme achieves significantly lower errors with the same computational efforts and less downlink communication while being inferior in terms of speed.