Matching Pursuit Based Scheduling for Over-the-Air Federated Learning

Abstract

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 (N^2+K)^3 + N^6 while the complexity of the proposed scheme scales with K^p N^q for some 0 < p,q 2. The efficiency of the proposed scheme is confirmed via numerical experiments on the CIFAR-10 dataset.

Tasks

Reproductions