Over-the-Air Computation in Correlated Channels

Matthias Frey, Igor Bjelakovic, Slawomir StanczakIEEE TSP 2021 · DOI

TL;DR

This paper introduces a novel analog Over-the-Air (OTA) computation scheme that can compute a broader class of functions (including non-linear ones like p-norms) than previous methods, even in the presence of correlated fading and noise. This advancement is crucial for efficient distributed machine learning in wireless networks, offering better scaling of communication costs.

What Problem Does This Paper Address?

The increasing number of wireless devices, especially in the Internet of Things (IoT) and future 6G networks, creates a significant demand for efficient data processing and communication. Traditional approaches often require transmitting all raw data to a central point for computation, which is communication-intensive and energy-consuming. Over-the-Air (OTA) computation offers a solution by computing functions of distributed data directly over the wireless channel, avoiding costly full data transmissions. However, existing OTA schemes often rely on strong assumptions about channel conditions (e.g., uncorrelated, Gaussian fading and noise) and are limited to simpler functions, primarily linear ones. This paper addresses the need for more robust and versatile OTA computation methods that can handle realistic, often correlated and non-Gaussian, wireless channel environments and compute a wider range of functions relevant to applications like distributed machine learning.

Methods

The core of this work is an analog OTA computation scheme that leverages a nomographic function representation. The key innovations include:

  • Generalized Channel Model: The analysis is performed under a channel model that accommodates sub-Gaussian random variables for fading and noise, allowing for arbitrary correlation structures. This is a significant departure from prior work that typically assumed independent and identically distributed (i.i.d.) Gaussian channels.
  • Non-Asymptotic Error Analysis: The paper provides error bounds that are valid for a finite number of channel uses, offering a more practical understanding of performance compared to asymptotic analyses.
  • Broader Function Class: The scheme is designed to compute functions belonging to the class $F_{mon}$, which includes linear functions as well as certain non-linear functions like p-norms. This is achieved through a combination of inner functions ($f_k$), a scaling and power constraint, and a random phase shift at each transmitter, followed by an outer function ($F$) at the receiver.
  • Pre- and Post-Processing: The scheme involves pre-processing at the transmitters (applying $f_k$, scaling, and random phase shifts) and post-processing at the receiver (energy computation, noise subtraction, rescaling, and applying $F$). These operations are designed to be robust to channel uncertainties.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations using synthetically generated data for classification problems.

Key Insights and Ideas

  • Robustness to Correlation is Key: The paper demonstrates that by carefully designing the OTA computation scheme and its analysis, it's possible to achieve reliable function computation even when wireless channels exhibit correlations, a common scenario in real-world deployments.
  • Beyond Linearity: The ability to compute non-linear functions like p-norms OTA opens up new possibilities for distributed machine learning tasks that go beyond simple aggregation or weighted sums.
  • Trade-offs in Communication Cost: The analysis provides explicit bounds on the communication cost (number of channel uses) required for a given accuracy and confidence level, highlighting the trade-offs involved.
  • Practical Relevance of Sub-Gaussian Models: The use of sub-Gaussian distributions for fading and noise makes the theoretical results applicable to a wider range of real-world interference and channel conditions than traditional Gaussian models.

Key Results

The paper presents a theoretical framework and derived bounds for OTA computation under generalized channel conditions.

  • Error Bounds: Theorem 1 provides non-asymptotic error bounds for approximating functions in $F_{mon}$. These bounds are shown to decrease exponentially with the number of channel uses ($M$), indicating efficient communication scaling.
  • Application to ML: The framework is applied to distributed machine learning problems, specifically in the context of Vertical Federated Learning (VFL). Simulations demonstrate that the proposed OTA-computed classifiers (e.g., Decision Trees, AdaBoost) achieve competitive performance compared to TDMA-based schemes, often with significantly fewer channel uses.
  • Performance Gains: Simulations show that the proposed DFA scheme can achieve substantial gains in terms of classification error and communication efficiency, especially as the number of transmitters increases. For instance, in some scenarios, the DFA scheme requires considerably fewer channel uses than TDMA for comparable error levels.
  • Synchronization Tolerance: The scheme is shown to be relatively robust to synchronization errors, a critical practical consideration for distributed wireless systems.

Limitations and Future Work

  • Sharpness of Bounds: The authors acknowledge that the derived error bounds are not necessarily sharp and suggest that further research could focus on optimizing these bounds, potentially by refining the statistical tools used.
  • Generalizing Training: While the paper focuses on OTA computation for prediction/classification, it suggests investigating how OTA computation can be leveraged for distributed training in Horizontal FL.
  • MIMO Systems and CSI: The paper mentions prior work on MIMO systems and CSI at the receiver, and suggests exploring the case of no CSI in MIMO systems for non-asymptotic characterizations.
  • Channel Shaping: The potential of using Intelligent Reflecting Surfaces (IRSs) to optimize OTA computation performance by shaping wireless channels is identified as an interesting avenue for future research.
  • Privacy Guarantees: For ML applications, formalizing and strengthening privacy guarantees in the context of OTA-computed ML predictors is an open question.

Summary updated

BibTeX
@article{frey2021over,
  author = {Matthias Frey and Igor Bjelakovic and Slawomir Stanczak},
  title = {{Over-the-Air Computation in Correlated Channels}},
  journal = {IEEE TSP},
  year = {2021},
  doi = {10.1109/tsp.2021.3106115},
}
Figure