How to Coordinate Edge Devices for Over-the-Air Federated Learning?

Mohammad Ali Sedaghat, Ali Bereyhi, Saba Asaad, Ralf R. MüllerarXiv 2022 · DOI · OpenReview

Abstract

Over-the-Air Federated Learning (OTA-FL) offers a bandwidth-efficient alternative to traditional Federated Learning by allowing simultaneous device transmissions. However, coordinating these transmissions to minimize aggregation error under power constraints is a complex combinatorial problem. This paper demonstrates that finding the optimal coordination strategy is NP-hard and proposes two low-complexity, tree-based algorithms: Approximate Zero-Forcing (AZF) and Approximate Minimum Mean Squared Error (AMMSE). Simulations show that these algorithms achieve near-optimal performance while significantly reducing computational overhead from exponential to polynomial complexity.

Introduction

In Federated Learning (FL), edge devices collaboratively train a global model without sharing raw data. While traditional FL requires separate wireless channels for each device, Over-the-Air Federated Learning (OTA-FL) utilizes the natural superposition property of the wireless medium to aggregate model updates simultaneously. Despite its efficiency, OTA-FL is sensitive to channel noise and varying signal strengths. The Parameter Server (PS) must coordinate device transmissions—deciding which devices should transmit at full power and how to scale others—to minimize the Mean Squared Error (MSE) of the aggregated result. This paper addresses the challenge of finding an optimal coordination strategy in real-time.

Methodology: Tree-Based Subset Selection

The researchers frame the coordination problem as a "subset selection" task: identifying which subset of devices should transmit at their maximum power limit ($P$) to minimize total error. They focus on two strategies: Zero-Forcing (ZF), which eliminates interference, and Minimum Mean Squared Error (MMSE), which balances interference and noise.

A key contribution is the identification of a monotonic property in the aggregation error, allowing the search space to be represented as a tree. Instead of an exhaustive search of all $2^L$ combinations for $L$ devices, the proposed AZF and AMMSE algorithms employ a greedy, tree-based search.

A tree-based search structure for selecting optimal device subsets to minimize aggregation error.

These algorithms start at the root (representing all devices) and traverse down the branches, removing one device at a time to find a feasible path that minimizes error. This approach reduces computational complexity from exponential to $O(L^2)$, making it suitable for dense edge networks.

Performance Evaluation

The proposed algorithms were evaluated using numerical simulations with i.i.d. Rayleigh fading channels. The study compared AZF and AMMSE against optimal exhaustive search benchmarks in both symmetric (equal pathloss) and asymmetric (unequal pathloss) scenarios.

Aggregation error vs. SNR for optimal and approximate (AZF/AMMSE) coordination strategies.

The results indicate that AZF and AMMSE "closely track" the performance of optimal schemes across a wide range of Signal-to-Noise Ratios (SNR). Notably, the MMSE-based approach proved more robust than ZF in asymmetric networks, where a single "weak link" device can otherwise bottleneck the entire aggregation process. Furthermore, the computational efficiency of these algorithms improves as the number of antennas at the PS increases, as channels become more orthogonal.

Conclusion and Future Directions

This work provides a scalable solution for device coordination in OTA-FL. By leveraging the tree-like structure of the error minimization problem, the AZF and AMMSE algorithms offer a practical path toward high-accuracy, low-latency federated learning at the edge.

Future research should address the impact of imperfect Channel State Information (CSI) and extend the model to wide-band systems with frequency-selective fading. Additionally, testing these coordination strategies within a full training loop on standard machine learning datasets will be crucial for validating their impact on final model convergence.

Summary updated

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.
BibTeX
@misc{sedaghat2022how,
  author = {Mohammad Ali Sedaghat and Ali Bereyhi and Saba Asaad and Ralf R. Müller},
  title = {{How to Coordinate Edge Devices for Over-the-Air Federated Learning?}},
  year = {2022},
  eprint = {2211.03449},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.03449},
}
Figure