A Lyapunov-based client selection approach to handle system-induced heterogeneity in federated learning

With the proliferation of smart devices and intelligent applications, there is an increasing concern about data privacy protection. To better protect users’ privacy when utilizing their data to train machine learning models, a promising paradigm called federated learning (FL) emerges, enabling model training without uploading the local data to the public server. However, in FL, as device capacities of different clients and network conditions can be inherently heterogeneous, the “straggler” problem arises which results in poor model performance and low system efficiency. Most existing methods either only focus on optimizing the training time or simply considering improving model accuracy, yet they fail to address both aspects in a coordinated manner. In this paper, we formulate an optimization problem to take into account both latency and clients’ contribution to the model training, while satisfying fairness and energy consumption constraints. To tackle this issue, we propose a Lyapunov optimization-based algorithm and devise a novel System Heterogeneity and Individual Reputation-aware Client Selection (SHIR-CS) algorithm. Specifically, we propose a historical time decay-based method and a reputation-based method to effectively evaluate clients’ latency and contribution, respectively. Then based on this, we leverage the Lyapunov framework to transform the problem into the drift-plus-penalty form and design an online algorithm. Extensive experiments on three well-known datasets demonstrate an effective trade-off between learning performance and training efficiency in comparison with state-of-the-art baselines.