# Optimal Compression of Locally Differentially Private Mechanisms

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 48 references that are in the map.
- First posted on arXiv 29 Oct 2021.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters](https://mlsanity.com/paper/1810.00440/) (2018)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [rTop-k: A Statistical Estimation Approach to Distributed SGD](https://mlsanity.com/paper/2005.10761/) (2020)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy](https://mlsanity.com/paper/1606.05053/) (2016)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters](https://mlsanity.com/paper/1905.11888/) (2019)
- [Locally Differentially Private Data Collection and Analysis](https://mlsanity.com/paper/1906.01777/) (2019)
- [Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints](https://mlsanity.com/paper/2106.08597/) (2021)

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

- [Compression with Bayesian Implicit Neural Representations](https://mlsanity.com/paper/2305.19185/) (2023)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Compression with Exact Error Distribution for Federated Learning](https://mlsanity.com/paper/2310.20682/) (2023)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Communication Efficient Private Federated Learning Using Dithering](https://mlsanity.com/paper/2309.07809/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Universal Exact Compression of Differentially Private Mechanisms](https://mlsanity.com/paper/2405.20782/) (2024)
- [Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design](https://mlsanity.com/paper/2211.03942/) (2022)
- [Adaptive Compression in Federated Learning via Side Information](https://mlsanity.com/paper/2306.12625/) (2023)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Some Notes on the Sample Complexity of Approximate Channel Simulation](https://mlsanity.com/paper/2405.04363/) (2024)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- [Breaking the Communication-Privacy-Accuracy Tradeoff with f-Differential Privacy](https://mlsanity.com/paper/2302.09624/) (2023)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Scalable Differentially Private Data Compression via Diffusion and Stochastic Codes](https://mlsanity.com/paper/2607.03392/) (2026)
- [Communication-Efficient and Privacy-Adaptable Mechanism for Federated Learning](https://mlsanity.com/paper/2501.12046/) (2025)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [Communication-Efficient and Privacy-Adaptable Mechanism -- a Federated Learning Scheme with Convergence Analysis](https://mlsanity.com/paper/2601.10701/) (2026)
- [Deep Randomized Distributed Function Computation (DeepRDFC): Neural Distributed Channel Simulation](https://mlsanity.com/paper/2603.10750/) (2026)
- [Secure Rate-Distortion-Perception: A Randomized Distributed Function Computation Approach for Realism](https://mlsanity.com/paper/2604.20245/) (2026)
- [Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacy](https://mlsanity.com/paper/2609.12067/) (2026)

## Abstract (arXiv)

Compressing the output of ε-locally differentially private (LDP) randomizers naively leads to suboptimal utility. In this work, we demonstrate the benefits of using schemes that jointly compress and privatize the data using shared randomness. In particular, we investigate a family of schemes based on Minimal Random Coding (Havasi et al., 2019) and prove that they offer optimal privacy-accuracy-communication tradeoffs. Our theoretical and empirical findings show that our approach can compress PrivUnit (Bhowmick et al., 2018) and Subset Selection (Ye et al., 2018), the best known LDP algorithms for mean and frequency estimation, to to the order of ε-bits of communication while preserving their privacy and accuracy guarantees.