# Matching Pursuit Based Scheduling for Over-the-Air Federated Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 89 references that are in the map.
- First posted on arXiv 14 Jun 2022.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Federated Learning on Non-IID Data Silos: An Experimental Study](https://mlsanity.com/paper/2102.02079/) (2021)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [Think Locally, Act Globally: Federated Learning with Local and Global Representations](https://mlsanity.com/paper/2001.01523/) (2020)
- [Federated Learning for Internet of Things: A Comprehensive Survey](https://mlsanity.com/paper/2104.07914/) (2021)
- [No Fear of Heterogeneity: Classifier Calibration for Federated Learning with Non-IID Data](https://mlsanity.com/paper/2106.05001/) (2021)
- [Edge Intelligence: Paving the Last Mile of Artificial Intelligence with Edge Computing](https://mlsanity.com/paper/1905.10083/) (2019)
- [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)
- [Energy Efficient Federated Learning Over Wireless Communication Networks](https://mlsanity.com/paper/1911.02417/) (2019)
- [Threats to Federated Learning: A Survey](https://mlsanity.com/paper/2003.02133/) (2020)
- [Scheduling Policies for Federated Learning in Wireless Networks](https://mlsanity.com/paper/1908.06287/) (2019)
- [Overcoming Forgetting in Federated Learning on Non-IID Data](https://mlsanity.com/paper/1910.07796/) (2019)
- [UVeQFed: Universal Vector Quantization for Federated Learning](https://mlsanity.com/paper/2006.03262/) (2020)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [Communication-Efficient Edge AI: Algorithms and Systems](https://mlsanity.com/paper/2002.09668/) (2020)
- [Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning](https://mlsanity.com/paper/2007.07174/) (2020)
- [On Analog Gradient Descent Learning over Multiple Access Fading Channels](https://mlsanity.com/paper/1908.07463/) (2019)
- [Fast-Convergent Federated Learning](https://mlsanity.com/paper/2007.13137/) (2020)
- [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021)
- [Optimized Power Control Design for Over-the-Air Federated Edge Learning](https://mlsanity.com/paper/2106.09316/) (2021)
- [Wireless Communications for Collaborative Federated Learning](https://mlsanity.com/paper/2006.02499/) (2020)
- [Federated Learning with Local Differential Privacy: Trade-offs between Privacy, Utility, and Communication](https://mlsanity.com/paper/2102.04737/) (2021)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)

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

- [A Survey on Over-the-Air Computation](https://mlsanity.com/paper/2210.11350/) (2022)

## Abstract (arXiv)

This paper develops a class of low-complexity device scheduling algorithms for over-the-air federated learning via the method of matching pursuit. The proposed scheme tracks closely the close-to-optimal performance achieved by difference-of-convex programming, and outperforms significantly the well-known benchmark algorithms based on convex relaxation. Compared to the state-of-the-art, the proposed scheme poses a drastically lower computational load on the system: For K devices and N antennas at the parameter server, the benchmark complexity scales with left(N2+Kright)3 + N6 while the complexity of the proposed scheme scales with Kp Nq for some 0 < p,q ≤ 2. The efficiency of the proposed scheme is confirmed via numerical experiments on the CIFAR-10 dataset.