Toward Efficient Semi-Asynchronous Federated Learning: A Multi-Factor Grouping and Dual-Level Selection Scheme Under Heterogeneous Environments

Abstract

Semi-Asynchronous Federated Learning (SAFL) takes advantage of both synchronous and asynchronous FLs to train models. However, existing works in semi-asynchronous FLs fail to fully account for heterogeneities in both data and devices. To address these issues, we first propose a Clustered SAFL (CSAFL) framework and theoretically analyze its convergence loss. Then, a convergence loss minimization problem is formulated under the considerations of heterogeneities in device resources, fairness of cluster selection, and data heterogeneity. To address this complex problem due to nonlinearities and multi-dimensional decision variables, we first design a device clustering algorithm based on both devices’ model parameter differences and gradient directions between local and global models. Then, the original loss minimization problem is transformed into inter- and intra-cluster selection problems. For the inter-cluster selection problem, to ensure fairness, we propose a reinforcement learning-driven Lyapunov approach to fairly select clusters, where reinforcement learning (RL) is used to supervise the cluster selection results by the Lyapunov method. For the intra-cluster selection, we convert it into a constrained multi-armed bandit (MAB) problem in order to let devices within a cluster submit models synchronously. Then, a two-stage Upper Confidence Bound (UCB) scheme is proposed to obtain device selection results. Extensive numerical results with baselines show that our approach achieves up to 25% higher accuracy.