# FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2020.

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

- [Privacy-Preserving Machine Learning: Methods, Challenges and Directions](https://mlsanity.com/paper/2108.04417/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [Privacy and Fairness in Federated Learning: on the Perspective of Trade-off](https://mlsanity.com/paper/2306.14123/) (2023)
- [Toward Communication Efficient Adaptive Gradient Method](https://mlsanity.com/paper/2109.05109/) (2021)
- [On Distributed Adaptive Optimization with Gradient Compression](https://mlsanity.com/paper/2205.05632/) (2022)
- [Optimizing the Communication-Accuracy Trade-off in Federated Learning with Rate-Distortion Theory](https://mlsanity.com/paper/2201.02664/) (2022)
- [OPORP: One Permutation + One Random Projection](https://mlsanity.com/paper/2302.03505/) (2023)
- [Federated Select: A Primitive for Communication- and Memory-Efficient Federated Learning](https://mlsanity.com/paper/2208.09432/) (2022)
- [Federated Dynamical Low-Rank Training with Global Loss Convergence Guarantees](https://mlsanity.com/paper/2406.17887/) (2024)
- [LASER: Linear Compression in Wireless Distributed Optimization](https://mlsanity.com/paper/2310.13033/) (2023)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Analysis of Error Feedback in Federated Non-Convex Optimization with Biased Compression](https://mlsanity.com/paper/2211.14292/) (2022)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [FedMPDD: Communication-Efficient Federated Learning with Privacy Preservation Attributes via Projected Directional Derivative](https://mlsanity.com/paper/2512.20814/) (2025)
- [Federated Gradient Matching Pursuit](https://mlsanity.com/paper/2302.10755/) (2023)
- [FedRP: A Communication-Efficient Approach for Differentially Private Federated Learning Using Random Projection](https://mlsanity.com/paper/2509.10041/) (2025)
- [ELSA: Efficient LLM-Centric Split Aggregation for Privacy-Aware Hierarchical Federated Learning over the Network Edge](https://mlsanity.com/paper/2601.13824/) (2026)

## Abstract (arXiv)

Communication complexity and privacy are the two key challenges in Federated Learning where the goal is to perform a distributed learning through a large volume of devices. In this work, we introduce FedSKETCH and FedSKETCHGATE algorithms to address both challenges in Federated learning jointly, where these algorithms are intended to be used for homogeneous and heterogeneous data distribution settings respectively. The key idea is to compress the accumulation of local gradients using count sketch, therefore, the server does not have access to the gradients themselves which provides privacy. Furthermore, due to the lower dimension of sketching used, our method exhibits communication-efficiency property as well. We provide, for the aforementioned schemes, sharp convergence guarantees. Finally, we back up our theory with various set of experiments.