Matching Pursuit Based Scheduling for Over-the-Air Federated Learning
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 poses a drastically lower computational
load on the system: For $K$ devices and $N$ antennas at the parameter server,
the benchmark complexity scales with $\left(N^2+K\right)^3 + N^6$ while the
complexity of the proposed scheme scales with $K^p N^q$ for some $0 < p,q \leq
2$. The efficiency of the proposed scheme is confirmed via numerical
experiments on the CIFAR-10 dataset.