# Communication-Efficient Federated Learning over Wireless Channels via Gradient Sketching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 45 references that are in the map.
- First posted on arXiv 30 Oct 2024.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Federated Learning on Non-IID Data Silos: An Experimental Study](https://mlsanity.com/paper/2102.02079/) (2021)
- [Federated Learning with Matched Averaging](https://mlsanity.com/paper/2002.06440/) (2020)
- [Bayesian Nonparametric Federated Learning of Neural Networks](https://mlsanity.com/paper/1905.12022/) (2019)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [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)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Communication-efficient distributed SGD with Sketching](https://mlsanity.com/paper/1903.04488/) (2019)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization](https://mlsanity.com/paper/1806.08054/) (2018)
- [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Federated Learning with Only Positive Labels](https://mlsanity.com/paper/2004.10342/) (2020)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [Error Compensated Distributed SGD Can Be Accelerated](https://mlsanity.com/paper/2010.00091/) (2020)
- [Robust Federated Learning with Noisy Communication](https://mlsanity.com/paper/1911.00251/) (2019)
- [Over-the-air Function Computation in Sensor Networks](https://mlsanity.com/paper/1612.02307/) (2016)
- [MISSION: Ultra Large-Scale Feature Selection using Count-Sketches](https://mlsanity.com/paper/1806.04310/) (2018)
- [Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach](https://mlsanity.com/paper/2102.07972/) (2021)
- [Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs](https://mlsanity.com/paper/1711.00987/) (2017)

## Abstract (arXiv)

Large-scale federated learning (FL) over wireless multiple access channels (MACs) has emerged as a crucial learning paradigm with a wide range of applications. However, its widespread adoption is hindered by several major challenges, including limited bandwidth shared by many edge devices, noisy and erroneous wireless communications, and heterogeneous datasets with different distributions across edge devices. To overcome these fundamental challenges, we propose Federated Proximal Sketching (FPS), tailored towards band-limited wireless channels and handling data heterogeneity across edge devices. FPS uses a count sketch data structure to address the bandwidth bottleneck and enable efficient compression while maintaining accurate estimation of significant coordinates. Additionally, we modify the loss function in FPS such that it is equipped to deal with varying degrees of data heterogeneity. We establish the convergence of the FPS algorithm under mild technical conditions and characterize how the bias induced due to factors like data heterogeneity and noisy wireless channels play a role in the overall result. We complement the proposed theoretical framework with numerical experiments that demonstrate the stability, accuracy, and efficiency of FPS in comparison to state-of-the-art methods on both synthetic and real-world datasets. Overall, our results show that FPS is a promising solution to tackling the above challenges of FL over wireless MACs.