Auction-based client selection for online Federated Learning

Federated Learning (FL) has become a popular decentralized learning paradigm to train a machine learning model using distributed mobile devices without compromising user privacy. Despite its advantages, there are several technical challenges to achieving efficient FL. First, clients may have different amount of data with various quality, thus leading to different quality of model updates. In an online setting, it is challenging to select clients having high-quality models in advance or to adjust the selection on the fly. Second, it is an impractical assumption that the clients can selflessly engage in model training without incentives. Meanwhile, the training cost is often considered as private information which is not easily accessible. Under incomplete information, how we design an effective incentive mechanism to achieve the expected economic properties? Third, due to the lack of prior knowledge, managing long-run expenditures in real time is challenging. To this end, we propose a combinatorial multi-armed bandit- and auction-based client selection algorithm named CACS to achieve highly efficient model training. Specifically, CACS divides the client selection process into exploration and exploitation. In the former, CACS employs the upper confidence bound (UCB) quality to estimate the learning quality of clients. In the latter, CACS determines winners based on the UCB quality-bid-ratio and adopts the key payment as the payment. Theoretical analysis shows that CACS obtains the sub-linear regret and economic properties, and can be computationally efficient and ensure the convergence of global model. Extensive simulation experiments also confirm the practical advantages of CACS over state-of-the-art client selection approaches for FL.