Fundamental limits of over-the-air optimization: Are analog schemes optimal?

Shubham K. Jha, Prathamesh Mayekar, Himanshu Tyagi

Distributed machine learning and federated learning rely heavily on the efficient exchange of gradient updates between edge devices and central servers. While traditional approaches treat communication and optimization as separate layers, "over-the-air" (OTA) computation has emerged as a promising alternative. OTA leverages the superposition property of wireless channels to aggregate gradients directly in the analog domain. However, a critical question remains: are these analog schemes truly optimal?

This research investigates the fundamental information-theoretic limits of convex optimization over noisy Additive White Gaussian Noise (AWGN) channels. The findings demonstrate that while analog schemes are efficient in low-signal-to-noise ratio (SNR) environments, they face a significant performance ceiling in high-SNR regimes—a bottleneck that only sophisticated digital schemes can overcome.

Establishing the Speed Limit of Optimization

To determine the "speed limit" for optimization over noisy channels, the researchers combined techniques from information theory and optimization. They derived a lower bound for the convergence rate of any possible algorithm by constructing "difficult" objective functions and oracles.

The analysis reveals that any communication-constrained optimization process must face a slowdown factor related to the dimensionality of the problem ($d$) and the channel capacity. Specifically, the theoretical lower bound suggests that the convergence rate is constrained by a factor of $\sqrt{d / \log(1 + \text{SNR})}$. This formula highlights the critical interplay between the complexity of the model and the quality of the communication link.

The $\sqrt{d}$ Analog Bottleneck

One of the paper's most significant contributions is identifying the "hard ceiling" of analog transmission. In a standard analog scheme, gradients are scaled to meet power constraints and transmitted directly. While intuitive, this approach fails to exploit the increased capacity of high-SNR channels.

The authors prove that analog schemes suffer from a convergence slowdown of $\sqrt{d(1 + 1/\text{SNR})}$. Even as SNR approaches infinity, the $\sqrt{d}$ term remains. This means that in high-dimensional settings (where $d$ is large), analog schemes will always be significantly slower than noiseless optimization, regardless of how much power is available. Analog schemes essentially fail to "pack" information more efficiently as the channel noise decreases.

Overcoming the Limit: Quantize-and-Modulate

To bridge the gap between analog performance and the theoretical lower bound, the authors propose a Quantize-and-Modulate digital scheme. This approach utilizes two key components:

  1. Gain-Shape Quantization: Instead of quantizing the entire gradient vector at once, the scheme separates the magnitude (gain) from the direction (shape). This separation allows for more efficient representation of high-dimensional vectors.
  2. Adaptive Amplitude Shift Keying (ASK): The quantized values are transmitted using ASK, where the resolution (the number of bits) scales logarithmically with the SNR ($r \approx \log(\text{SNR})$).

By increasing the quantization resolution as the channel quality improves, this digital scheme can effectively bypass the $\sqrt{d}$ bottleneck and approach the performance of a noiseless channel at high SNR.

Empirical Validation on MNIST

The researchers validated their theoretical findings by training a 3-layer Convolutional Neural Network (CNN) on the MNIST dataset. The model contained approximately 27,210 parameters ($d \approx 2.7 \times 10^4$). The experiments compared the analog scheme against the proposed ASK-based digital scheme across a wide range of SNR levels:

  • Low SNR (-30dB): In high-noise environments, the simple analog scheme outperformed the digital approach. At this level, the overhead and quantization errors of digital coding outweigh its benefits, making analog scaling the optimal choice.
  • High SNR (100dB to 180dB): As the SNR increased, the digital scheme's superiority became clear. While the analog scheme's performance plateaued due to the $\sqrt{d}$ bottleneck, the ASK-based scheme continued to improve, eventually matching the "baseline" performance of a noiseless channel.
  • Intermediate SNR (40dB): At moderate power levels, the two schemes performed similarly, representing the transition point where digital coding begins to provide a competitive advantage.

Conclusion and Future Directions

The study concludes that the optimality of over-the-air optimization is SNR-dependent. Analog schemes are "rate-optimal" only in the low-SNR regime. For high-precision optimization and high-SNR channels, digital "quantize-and-modulate" schemes are necessary to achieve the fundamental limits of the channel.

While this work focuses on a single-user scenario, it provides a rigorous foundation for future research into Multi-Access Channels (MAC). Future work may involve implementing "lattice codes" to extend these digital benefits to multi-user federated learning environments, where multiple devices transmit simultaneously over the air.

Summary updated

BibTeX
@article{jha2022fundamental,
  author = {Shubham K. Jha and Prathamesh Mayekar and Himanshu Tyagi},
  title = {{Fundamental limits of over-the-air optimization: Are analog schemes optimal?}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2022},
  doi = {10.1109/jsait.2022.3177582},
}
Figure