Device Scheduling in Over-the-Air Federated Learning Via Matching Pursuit
Ali Bereyhi, Adela Vagollari, Saba Asaad, Ralf R. Müller, Wolfgang Gerstacker, H. Vincent Poor · IEEE Transactions on Signal Processing · 2023
This paper develops a class of low-complexity device scheduling algorithms for over-the-air federated learning via the method of matching pursuit. The proposed scheme tracks closely theclose-to-optimalperformance achieved by difference-of-convex programming, and outperforms significantly the well-known benchmark algorithms based on convex relaxation. Compared to the state-of-the-art, the proposed scheme imposes a drastically lower computational load on the system: for$K$devices and$N$antennas at the parameter server, the benchmark complexity scales with$(N^{2}+K)^{3} + N^{6}$while the complexity of the proposed scheme scales with${K^{p} N^{q}}$for some$0 \lt p,q \leq 2$. The efficiency of the proposed scheme is confirmed through the convergence analysis and numerical experiments on CIFAR-10 dataset.