Device Scheduling in Over-the-Air Federated Learning Via Matching Pursuit

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 the close-to-optimal performance 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 (KNq)-N-p for some 0 < p, q <= 2. The efficiency of the proposed scheme is confirmed through the convergence analysis and numerical experiments on CIFAR-10 dataset.