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

Ali Bereyhi, Adela Vagollari, Saba Asaad, Ralf R. Müller, Wolfgang H. Gerstacker, H. Vincent Poor

Introduction

Federated Learning (FL) has emerged as a critical paradigm for distributed artificial intelligence, enabling numerous edge devices to collaboratively train a global model while keeping their local data private. Despite its advantages, FL faces a significant "communication bottleneck." As the number of participating devices grows, the time and energy required to transmit high-dimensional model updates over wireless links can become prohibitive.

Traditional FL systems utilize orthogonal communication, where each device is allocated a unique frequency or time slot. However, this approach scales poorly. Over-the-Air Federated Learning (OTA-FL) offers a promising alternative by leveraging the superposition property of wireless channels. In OTA-FL, devices transmit simultaneously, and the wireless medium itself performs the aggregation (summation) of signals. While efficient, OTA-FL is highly sensitive to channel fading and noise. To maintain model accuracy, the system must perform device scheduling—selecting a subset of devices with favorable channel conditions. This paper proposes a novel scheduling framework based on the Matching Pursuit (MP) algorithm to achieve near-optimal performance with drastically reduced computational overhead.

The Scheduling Challenge in OTA-FL

The goal of device scheduling in OTA-FL is to minimize the "computation error"—the difference between the ideal aggregated update and the noisy version received at the base station. Finding the optimal subset of devices is an NP-hard combinatorial problem.

Existing solutions typically fall into two categories: high-complexity optimization and low-performance heuristics. State-of-the-art methods like Difference-of-Convex (DC) programming provide high accuracy but are computationally intensive, making them unsuitable for real-time execution on resource-constrained edge controllers. Conversely, simpler methods like random scheduling often fail to meet the stringent error requirements necessary for model convergence. There is a clear need for an algorithm that balances the precision of DC programming with the speed of simple heuristics.

Proposed Methodology: Matching Pursuit Scheduling

The authors introduce a greedy scheduling algorithm inspired by Matching Pursuit, a technique traditionally used to find sparse representations of signals. The proposed approach focuses on three core components:

1. Backward Selection

Rather than building a set of devices from scratch, the algorithm employs a backward selection strategy. It begins with all available devices active and iteratively removes the device that contributes most significantly to the total aggregation error. This process continues until the remaining subset satisfies the system's error constraints.

2. Channel Alignment and Inner Products

A key insight of the paper is the use of channel alignment as a selection criterion. The algorithm identifies the "worst" device by calculating the inner product between each device's channel vector and the current linear receiver at the base station. The device with the least alignment is the primary candidate for removal, as its signal is most likely to be distorted by noise or to interfere with the aggregate update.

3. Subset-Cutting and Joint Tuning

To ensure rapid convergence, the authors implement a "subset-cutting" strategy. This involves a binary tuning mechanism where devices are weighted based on whether they satisfy or violate specific error thresholds. Furthermore, the paper extends this logic to Intelligent Reflecting Surface (IRS)-aided networks, where the algorithm jointly optimizes device selection and the phase shifts of the reflecting surface to further enhance signal quality.

Experimental Evaluation

The proposed MP-based scheduler was evaluated using the CIFAR-10 dataset, a standard benchmark for image classification. To reflect real-world edge computing environments, the researchers utilized a non-IID (Independent and Identically Distributed) data setup. This configuration included both "quantity skew" (varying amounts of data per device) and "label skew" (varying class distributions), creating a challenging environment for model aggregation.

Results and Discussion

The experimental results highlight a significant breakthrough in the trade-off between complexity and performance:

  • Computational Efficiency: The MP scheme achieves a massive reduction in complexity. While traditional benchmarks scale at $O((N^2+K)^3)$, the MP approach scales at approximately $O(K^2 N^2)$. In practical simulations, this reduced the scheduling runtime from 10 seconds to 0.0001 seconds—a $10^5$ speedup.
  • Learning Accuracy: Despite the greedy nature of the algorithm, the MP-based scheduler achieved classification accuracy nearly identical to the high-complexity DC programming benchmark.
  • System Efficiency: The scheme reached 98% efficiency compared to an idealized "Perfect FL" scenario (zero communication noise), demonstrating that low-complexity scheduling does not necessitate a sacrifice in model quality.

Conclusion

This research demonstrates that Matching Pursuit provides a highly effective framework for device scheduling in Over-the-Air Federated Learning. By replacing exhaustive optimization with a greedy, channel-aware selection process, the authors enable high-performance distributed learning on the edge with minimal latency.

Future work remains to address the requirement for perfect Channel State Information (CSI), which can be difficult to obtain in high-mobility scenarios. Additionally, exploring the robustness of this greedy approach against adversarial devices or hardware impairments will be essential for deploying OTA-FL in diverse, real-world environments.

Summary updated

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 $\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.
BibTeX
@article{bereyhi2023matching,
  author = {Ali Bereyhi and Adela Vagollari and Saba Asaad and Ralf R. Müller and Wolfgang H. Gerstacker and H. Vincent Poor},
  title = {{Matching Pursuit Based Scheduling for Over-the-Air Federated Learning}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  doi = {10.1109/tsp.2023.3284376},
}
Figure