A Contribution-Based Device Selection Scheme in Federated Learning

In a Federated Learning (FL) setup, a number of devices contribute to the training of a common model. We present a method for selecting the devices that provide updates in order to achieve improved generalization, fast convergence, and better device-level performance. We formulate a min-max optimization problem and decompose it into a primal-dual setup, where the duality gap is used to quantify the device-level performance. Our strategy combines exploration of data freshness through a random device selection with exploitation through simplified estimates of device contributions. This improves the performance of the trained model both in terms of generalization and personalization. A modified Truncated Monte-Carlo (TMC) method is applied during the exploitation phase to estimate the device’s contribution and lower the communication overhead. The experimental results show that the proposed approach has a competitive performance, with lower communication overhead and competitive personalization performance against the baseline schemes.

I. Introduction

Federated Learning (FL), as introduced by McMahan et. al. [1], discusses unbalanced and non-i.i.d. (independent and identical distribution) data partitioning across a massive number of unreliable devices, coordinating with a central server, to distributively train learning models without sharing the actual data. In practice, the data samples are generated through device’s usage, such as interactions with applications, results to such statistical heterogeneity. Towards that, related works primarily focus on improving the model performance by tackling data properties, i.e., statistical challenges in the FL [1], [2]. Noticeably, in the initial work [1], the authors show that their proposed Federated Averaging (FedAvg) algorithm empirically works well with non-i.i.d. data. However, the accuracy of FedAvg varies differently for different datasets, as observed in the existing methods [2], [3], and how client selection is made [3]–[5]. For instance, the authors in [3], [4], [6] discussed the impact of having heterogeneous clients, given time requirements for per round training execution, during the decentralized model training over unreliable wireless networks. In doing so, more devices are packed within a training round to improve model performance; however, this lead to consumption of excessive communication resources and larger communication rounds to attain a level of global model accuracy. Also, all received local updates are directly aggregated during model aggregation [1], [3], [6], [7]; thus, fairly ignoring their individual contributions and the rationale behind selecting them. In line with that, the authors in [1]–[3] revealed that adding local computations can dramatically increase communication efficiency and improve the trained model performance. However, this additional computational load may be prohibitive for some devices.