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

Conference: WSA & SCC 2023 - 26th International ITG Workshop on Smart Antennas and 13th Conference on Systems, Communications, and Coding
02/27/2023 at Braunschweig, Germany

Proceedings: ITG-Fb. 308: WSA & SCC 2023

Pages: 6Language: englishTyp: PDF

Authors:
Sedaghat, Mohammad Ali (Qualcomm CDMA Technologies GmbH Nuremberg, Germany)
Bereyhi, Ali; Mueller, Ralf R.; Asaad, Saba (Friedrich-Alexander Universität Erlangen-Nürnberg, Germany)

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.