A Novel Tree-Based Algorithm for Device Coordination in Over-the-Air Federated Learning

Abstract:
This work studies the task of device coordination in wireless networks for over-the-air federated learning (OTA-FL). For conventional metrics of aggregation error, the task is shown to describe the zero-forcing (ZF) and minimum mean squared error (MMSE) schemes and reduces to the NP-hard problem of subset selection. We tackle this problem by studying properties of the optimal scheme. Our analytical results reveal that this scheme is found by searching among the leaves of a tree with favorable monotonic features. Invoking these features, we develop a low-complexity algorithm that approximates the optimal scheme by tracking a dominant path of the tree sequentially. Our numerical investigations show that the proposed algorithm closely tracks the optimal scheme.