Interference-Robust Non-Coherent Over-the-Air Computation for Decentralized Optimization

1. Problem Statement

The paper addresses the challenge of decentralized optimization in wireless networks, specifically focusing on Decentralized Gradient Descent (DGD). In this setting, $N$ nodes collaboratively minimize a global objective function $F(w) = \frac{1}{N}\sum f_i(w)$ using only peer-to-peer communications, without a central aggregator.

• The Baseline: The authors previously proposed Non-Coherent Over-the-Air Computation (NCOTA). This method exploits the superposition property of wireless channels to estimate the "disagreement signal" (the difference between local parameters and the network average) without requiring Channel State Information (CSI) or transmission scheduling. It achieves unbiased estimation in the presence of noise and fading.
• The Limitation: NCOTA is inherently vulnerable to external interference (e.g., jamming, adversarial signals, or environmental noise). Unlike additive white Gaussian noise (which can be compensated for if its variance is known), external interference accumulates energy at the receiver. This introduces a bias (drift) into the disagreement signal estimate.
• The Consequence: If the estimate is biased, the DGD algorithm accumulates error over iterations, preventing convergence to the global optimum. The existing NCOTA scheme fails completely under active interference.

2. Methodology: Interference-Robust NCOTA (IR-NCOTA)

The paper proposes a novel scheme, IR-NCOTA, designed to restore the unbiased nature of the disagreement signal estimate even when external interference is present. The core strategy involves transforming the interference so that its contribution averages to zero over time.

The solution relies on two key mechanisms:

A. Coordinated Random Rotation of the Frame of Reference

• Concept: Instead of encoding local parameters $w_i$ in a fixed coordinate system, all nodes apply a coordinated random unitary transformation $U$ to their parameters before transmission.
• Implementation:
  • $U$ is a random matrix (e.g., a random sign flip $U = sI$ where $s \in \{+1, -1\}$) generated via a shared pseudo-random seed.
  • $U$ is statistically independent of the interference signal and changes at every iteration.
  • Nodes transmit the rotated vector $\tilde{w}_i = U w_i$.
• Effect: The interference, which is fixed or slowly varying relative to the signal, appears to rotate randomly in the receiver's frame of reference. When the receiver averages the estimates over iterations (or across the random realizations of $U$), the interference term becomes zero-mean, effectively canceling out the bias.

B. Pseudo-Random Pilot Sequence for Channel Gain Estimation

• Challenge: The DGD update requires estimating the sum of average channel gains ($\bar{\Lambda}_i = \sum_{j \neq i} \Lambda_{ij}$) to scale the local parameter correctly. In the presence of interference, standard energy-based estimation of channel gains becomes biased.
• Solution: Nodes transmit a pseudo-random pilot sequence $x_P$ with random phases $\phi_m$ (uniformly distributed over $[0, 2\pi]$).
• Mechanism:
  • The receiver computes a specific estimator using the pilot observations.
  • Due to the random phases, the cross-terms involving the interference and the pilot signal average to zero.
  • This allows the node to estimate the sum of channel gains $\bar{\Lambda}_i$ unbiasedly, even without knowing the interference statistics.

The Algorithm Flow

1. Rotation: Node $i$ rotates its local parameter: $\tilde{w}_i = U w_i$.
2. Encoding: $\tilde{w}_i$ is encoded into energy-based signals using the standard NCOTA mapping.
3. Transmission: Nodes transmit simultaneously (randomized by a probability $p_{tx}$).
4. Pilot Transmission: Nodes also send the random-phase pilot sequence to estimate channel gains.
5. Reception & Estimation:
   • The receiver estimates the weighted sum of rotated parameters ($\hat{s}_i$) and rotates it back: $U^\top \hat{s}_i$.
   • The receiver estimates the channel gain sum ($\hat{\Lambda}_i$) using the pilot.
   • The final disagreement signal is computed as: $\hat{d}_i = U^\top \hat{s}_i - \hat{\Lambda}_i w_i$.

3. Key Contributions

1. Identification of Failure Mode: The paper rigorously demonstrates that external interference breaks the unbiasedness condition of standard NCOTA, leading to DGD divergence.
2. Novel IR-NCOTA Scheme: Introduction of a framework that combines coordinated random rotations and random-phase pilots to neutralize arbitrary external interference.
3. Theoretical Guarantees: Proof that the proposed estimator is unbiased ($E[\hat{d}_i] = d_i$) regardless of the interference distribution (provided it is uncorrelated with the channel and pilot phases). This ensures the convergence guarantees of DGD ($O(1/\sqrt{k})$) remain valid.
4. Practicality: The scheme requires no Channel State Information (CSI) at transmitters or receivers and no transmission scheduling, maintaining the low-latency and bandwidth efficiency of the original NCOTA.

4. Numerical Results

The authors evaluated the scheme using a Fashion-MNIST classification task with $N=200$ nodes in a decentralized setting.

• Scenario 1: No Interference
  • IR-NCOTA performs comparably to the baseline NCOTA.
  • The lack of knowledge regarding noise variance ($N_0$) in IR-NCOTA did not significantly degrade performance.
• Scenario 2: Active Interference
  • Baseline NCOTA: Failed to converge. All metrics (normalized error, suboptimality gap, test error) hit a "floor," indicating a persistent deviation from the optimal solution due to interference-induced drift.
  • IR-NCOTA: Successfully converged. While the convergence rate was slightly slower than the interference-free case (due to increased variance in the estimates), the error metrics continued to decrease toward zero.
• Overhead: The proposed method introduced a minimal pilot overhead of approximately 1% (using a pilot length $n_P=10$), which is negligible compared to the performance gain.

5. Significance

This work is significant for the deployment of decentralized learning in harsh or contested environments (e.g., post-disaster scenarios, military operations, or remote areas with jamming).

• It extends the applicability of Over-the-Air (OTA) computation from idealized noise-limited channels to realistic interference-limited environments.
• It provides a robust solution that does not rely on complex interference cancellation techniques or centralized coordination, preserving the scalability and low-latency benefits of decentralized systems.
• It bridges the gap between theoretical convergence guarantees and practical wireless implementation under adversarial conditions.