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

arXiv: https://arxiv.org/abs/2109.05222 · HTML: https://mlsanity.com/paper/2109.05222/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 11 Sep 2021.

## Builds on (most cited first, 30 of 30)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [A Joint Learning and Communications Framework for Federated Learning over Wireless Networks](https://mlsanity.com/paper/1909.07972/) (2019)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Federated Learning via Over-the-Air Computation](https://mlsanity.com/paper/1812.11750/) (2018)
- [Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version)](https://mlsanity.com/paper/1812.11494/) (2018)
- [Federated Learning over Wireless Fading Channels](https://mlsanity.com/paper/1907.09769/) (2019)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysis](https://mlsanity.com/paper/2001.05713/) (2020)
- [Hierarchical Federated Learning Across Heterogeneous Cellular Networks](https://mlsanity.com/paper/1909.02362/) (2019)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2102.04487/) (2021)
- [On Analog Gradient Descent Learning over Multiple Access Fading Channels](https://mlsanity.com/paper/1908.07463/) (2019)
- [Adaptive Gradient Quantization for Data-Parallel SGD](https://mlsanity.com/paper/2010.12460/) (2020)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [Energy-Aware Analog Aggregation for Federated Learning with Redundant Data](https://mlsanity.com/paper/1911.00188/) (2019)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Distributed Newton Can Communicate Less and Resist Byzantine Workers](https://mlsanity.com/paper/2006.08737/) (2020)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [Communication Efficient Federated Learning over Multiple Access Channels](https://mlsanity.com/paper/2001.08737/) (2020)
- [Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach](https://mlsanity.com/paper/2102.07972/) (2021)
- [Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air](https://mlsanity.com/paper/1901.00844/) (2019)
- [Distributed Learning with Sublinear Communication](https://mlsanity.com/paper/1902.11259/) (2019)
- [Collaborative Machine Learning at the Wireless Edge with Blind Transmitters](https://mlsanity.com/paper/1907.03909/) (2019)
- [Information-constrained optimization: can adaptive processing of gradients help?](https://mlsanity.com/paper/2104.00979/) (2021)

## Built on by (most cited first, 3 of 3)

- [A Survey on Over-the-Air Computation](https://mlsanity.com/paper/2210.11350/) (2022)
- [Communication-Constrained Bandits under Additive Gaussian Noise](https://mlsanity.com/paper/2304.12680/) (2023)
- [Power-Constrained Policy Gradient Methods for LQR](https://mlsanity.com/paper/2507.15806/) (2025)

## Abstract (arXiv)

We consider over-the-air convex optimization on a d-dimensional space where coded gradients are sent over an additive Gaussian noise channel with variance σ2. The codewords satisfy an average power constraint P, resulting in the signal-to-noise ratio (SNR) of P/σ2. We derive bounds for the convergence rates for over-the-air optimization. Our first result is a lower bound for the convergence rate showing that any code must slowdown the convergence rate by a factor of roughly √d/log(1+mathttSNR). Next, we consider a popular class of schemes called analog coding, where a linear function of the gradient is sent. We show that a simple scaled transmission analog coding scheme results in a slowdown in convergence rate by a factor of √d(1+1/mathttSNR). This matches the previous lower bound up to constant factors for low SNR, making the scaled transmission scheme optimal at low SNR. However, we show that this slowdown is necessary for any analog coding scheme. In particular, a slowdown in convergence by a factor of √d for analog coding remains even when SNR tends to infinity. Remarkably, we present a simple quantize-and-modulate scheme that uses Amplitude Shift Keying and almost attains the optimal convergence rate at all SNRs.