Clients selection method based on knapsack model in federated learning

Abstract

In recent years, to break down data barriers, federated learning (FL) has received extensive attention.In FL, clientscan complete the model training without uploading the raw data, which protects the user’s data privacy.For the issue of clients’ heterogeneity, the contribution of each client to accelerating convergence of the global model as well as the communication cost in the system was considered, aiming at maximizing the weight change of the client's local training model, a client selection optimization problem in FL under theconstraint ofthe delay foreach training round was solved.Subsequently, two federated learning protocols based on the knapsack model were proposed, namely OfflineKP-FL protocol and OnlineKP-FL protocol.OfflineKP-FL protocol was based on the offline knapsack model to select appropriate clients to participate in the aggregation and update of the global model.In order to reduce the complexity of the OfflineKP-FL protocol, OnlineKP-FL protocol based on the online knapsack model to select clients was proposed.Through simulations, it is found that OfflineKP-FL protocol converges faster than the previously proposed methods in certain cases.Furthermore, compared with OfflineKP-FL protocol and FedCS protocol, underthe proposed OnlineKP-FL protocol, not only does the system select fewer clients per round, but also it can complete the model training in 64.1% of the time required by FedCS protocol to achieve the same accuracy for the global model.

Keywords

• federated learning;client selection;knapsack model