# Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2019.

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

- [Privacy-Preserving Machine Learning: Methods, Challenges and Directions](https://mlsanity.com/paper/2108.04417/) (2021)
- [Federated Learning with Sparsified Model Perturbation: Improving Accuracy under Client-Level Differential Privacy](https://mlsanity.com/paper/2202.07178/) (2022)
- [Privacy and Fairness in Federated Learning: on the Perspective of Trade-off](https://mlsanity.com/paper/2306.14123/) (2023)
- [Preserved central model for faster bidirectional compression in distributed settings](https://mlsanity.com/paper/2102.12528/) (2021)
- [Randomized Quantization is All You Need for Differential Privacy in Federated Learning](https://mlsanity.com/paper/2306.11913/) (2023)
- [On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates](https://mlsanity.com/paper/2106.07094/) (2021)
- [State-of-the-Art Approaches to Enhancing Privacy Preservation of Machine Learning Datasets: A Survey](https://mlsanity.com/paper/2404.16847/) (2024)
- [Collaborative Drug Discovery: Inference-level Data Protection Perspective](https://mlsanity.com/paper/2205.06506/) (2022)
- [Lossy Gradient Compression: How Much Accuracy Can One Bit Buy?](https://mlsanity.com/paper/2202.02812/) (2022)
- [Communication-Efficient Federated Learning with Adaptive Compression under Dynamic Bandwidth](https://mlsanity.com/paper/2405.03248/) (2024)
- [Communication-Efficient Adam-Type Algorithms for Distributed Data Mining](https://mlsanity.com/paper/2210.07454/) (2022)
- [M22: A Communication-Efficient Algorithm for Federated Learning Inspired by Rate-Distortion](https://mlsanity.com/paper/2301.09269/) (2023)
- [How to Attain Communication-Efficient DNN Training? Convert, Compress, Correct](https://mlsanity.com/paper/2204.08211/) (2022)
- [On the Interaction Between Differential Privacy and Gradient Compression in Deep Learning](https://mlsanity.com/paper/2211.00734/) (2022)
- [Compressive Meta-Learning](https://mlsanity.com/paper/2508.11090/) (2025)
- [Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learning](https://mlsanity.com/paper/2508.12978/) (2025)
- [Private Sketches for Linear Regression](https://mlsanity.com/paper/2511.07365/) (2025)

## Abstract (arXiv)

Communication and privacy are two critical concerns in distributed learning. Many existing works treat these concerns separately. In this work, we argue that a natural connection exists between methods for communication reduction and privacy preservation in the context of distributed machine learning. In particular, we prove that Count Sketch, a simple method for data stream summarization, has inherent differential privacy properties. Using these derived privacy guarantees, we propose a novel sketch-based framework (DiffSketch) for distributed learning, where we compress the transmitted messages via sketches to simultaneously achieve communication efficiency and provable privacy benefits. Our evaluation demonstrates that DiffSketch can provide strong differential privacy guarantees (e.g., varepsilon= 1) and reduce communication by 20-50x with only marginal decreases in accuracy. Compared to baselines that treat privacy and communication separately, DiffSketch improves absolute test accuracy by 5%-50% while offering the same privacy guarantees and communication compression.