  Federated learning (FL) is an emerging machine learning (ML) paradigm used to
train models across multiple nodes (i.e., clients) holding local data sets,
without explicitly exchanging the data. It has attracted a growing interest in
recent years due to its advantages in terms of privacy considerations, and
communication resources. In FL, selected clients train their local models and
send a function of the models to the server, which consumes a random processing
and transmission time. The server updates the global model and broadcasts it
back to the clients. The client selection problem in FL is to schedule a subset
of the clients for training and transmission at each given time so as to
optimize the learning performance. In this paper, we present a novel
multi-armed bandit (MAB)-based approach for client selection to minimize the
training latency without harming the ability of the model to generalize, that
is, to provide reliable predictions for new observations. We develop a novel
algorithm to achieve this goal, dubbed Bandit Scheduling for FL (BSFL). We
analyze BSFL theoretically, and show that it achieves a logarithmic regret,
defined as the loss of BSFL as compared to a genie that has complete knowledge
about the latency means of all clients. Furthermore, simulation results using
synthetic and real datasets demonstrate that BSFL is superior to existing
methods.
