mlsanityData to 7 Oct 2026

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

arXiv 2109.05222 ↗First posted 11 Sep 2021cs.IT cs.LG eess.SPcited by 2

Not on the map. Why?

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.

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

Builds on

30 of 51 references.

References · 30

  1. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  2. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  3. 2019A Joint Learning and Communications Framework for Federated Learning over Wireless Networkscited by 262
  4. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  5. 2018The Convergence of Sparsified Gradient Methodscited by 228
  6. 2018Federated Learning via Over-the-Air Computationcited by 215
  7. 2018Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version)cited by 186
  8. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  9. 2019Federated Learning over Wireless Fading Channelscited by 178
  10. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  11. 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 135
  12. 2016Distributed Mean Estimation with Limited Communicationcited by 134
18 more
  1. 2020One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysiscited by 108
  2. 2019Hierarchical Federated Learning Across Heterogeneous Cellular Networkscited by 98
  3. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  4. 2019On Analog Gradient Descent Learning over Multiple Access Fading Channelscited by 61
  5. 2021Adaptive Quantization of Model Updates for Communication-Efficient Federated Learningcited by 60
  6. 2020Adaptive Gradient Quantization for Data-Parallel SGDcited by 43
  7. 2018Inference under Information Constraints I: Lower Bounds from Chi-Square Contractioncited by 31
  8. 2019RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimizationcited by 23
  9. 2019Energy-Aware Analog Aggregation for Federated Learning with Redundant Datacited by 23
  10. 2020Unified lower bounds for interactive high-dimensional estimation under information constraintscited by 22
  11. 2020Distributed Newton Can Communicate Less and Resist Byzantine Workerscited by 20
  12. 2020Interactive Inference under Information Constraintscited by 15
  13. 2020Communication Efficient Federated Learning over Multiple Access Channelscited by 11
  14. 2021Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approachcited by 11
  15. 2019Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Aircited by 10
  16. 2019Distributed Learning with Sublinear Communicationcited by 9
  17. 2019Collaborative Machine Learning at the Wireless Edge with Blind Transmitterscited by 9
  18. 2021Information-constrained optimization: can adaptive processing of gradients help?cited by 8

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1.

2 papers.

  1. 2022A Survey on Over-the-Air Computationcited by 19
  2. 2023Communication-Constrained Bandits under Additive Gaussian Noisecited by 4