Research On Client Selection For Federated Learning Using Combinatorial Multi-Armed Bandit

A federated learning system usually includes a central server and a large number of clients.These clients often have different hardware configurations,different battery capacities,and different data set types and quality.In addition,due to diminishing marginal benefits,the central server cannot select all clients in a single round to participate in model training.This makes which clients are selected in each training epoch an important factor affecting the quality of the final models.In order to solve the client selection problem of federated learning system,this paper aims to optimize the training efficiency to solve the above problem.This paper proposes an Energy Aware Client Selection(EACS)algorithm based on the Combinatorial Multi-Armed Bandit(CMAB)framework,and combines the Lyapunov optimization method to deal with the client’s energy consumption.The main contributions of this paper are as follows:1.This paper formulates the problem under framework of CMAB,and the heterogeneous energy constraints of the client are handled by combining CMAB with Lyapunov optimization,thus,controlling the selection frequency of the client indirectly to ensure the balance of the selection.Since it is difficult for the central server to accurately judge clients’ training performance according to their hardware information,this paper adopts the idea of "exploring then exploitation" of the Upper Confidence Bound(UCB)algorithm to use the historical training performance of the clients to judge their performance.At the same time,the approximate optimal solution is obtained by transforming the original NP-hard problem into an online round-by-round optimization problem.2.According to the formulation of the problem,this paper designs the EACS algorithm.Considering the datasets held by clients may be different,this paper designs a matching algorithm between the client sets selected by the EACS algorithm and the global model according to datasets on clients.Through theoretical proof,the time-averaged regret of the EACS algorithm is sublinear,that is,the EACS algorithm can give a solution close to the optimal algorithm when the number of rounds is sufficient.This paper also verifies the stability of the virtual energy deficit queue of the client through theoretical proof,which effectively controls the energy consumption of the client.3.In order to evaluate the EACS algorithm,this paper builds a federated learning training platform based on the flower framework,and simulates a multi-clients environment through the docker engine.By comparing the experimental results with two benchmark algorithms,this paper evaluates the performance of the EACS algorithm.The experimental results show that the EACS algorithm can achieve better energy consumption performance than the two benchmark algorithms at the expense of a certain training delay performance.Meanwhile,the experimental results show that EACS does not adversely affect the final model’s accuracy.In addition,by adjusting the virtual energy deficit queue,the client selection frequency can be indirectly controlled to achieve a balanced selection.