mlsanityData to 7 Oct 2026

Optimal Compression of Locally Differentially Private Mechanisms

arXiv 2111.00092 ↗First posted 29 Oct 2021cs.CR cs.LGcited by 22

Not on the map. Why?

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.

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

Builds on

26 of 48 references.

References · 26

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  3. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  4. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  5. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 157
  6. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  7. 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 135
  8. 2016Distributed Mean Estimation with Limited Communicationcited by 134
  9. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 127
  10. 2019The Privacy Blanket of the Shuffle Modelcited by 73
  11. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  12. 2016Discrete Distribution Estimation under Local Privacycited by 58
14 more
  1. 2018Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameterscited by 56
  2. 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
  3. 2015Local, Private, Efficient Protocols for Succinct Histogramscited by 35
  4. 2018Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraintscited by 33
  5. 2017Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacycited by 28
  6. 2017Practical Locally Private Heavy Hitterscited by 28
  7. 2020rTop-k: A Statistical Estimation Approach to Distributed SGDcited by 27
  8. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  9. 2018Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communicationcited by 26
  10. 2016Collecting and Analyzing Data from Smart Device Users with Local Differential Privacycited by 25
  11. 2017Heavy Hitters and the Structure of Local Privacycited by 20
  12. 2019Communication Complexity in Locally Private Distribution Estimation and Heavy Hitterscited by 11
  13. 2019Locally Differentially Private Data Collection and Analysiscited by 5
  14. 2021Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraintscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 6; 2025: 1; 2026: 5.

22 papers.

Sort:

  1. 2023Compression with Bayesian Implicit Neural Representationscited by 25
  2. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  3. 2022Private Frequency Estimation via Projective Geometrycited by 9
  4. 2023Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimationcited by 9
  5. 2023Compression with Exact Error Distribution for Federated Learningcited by 9
  6. 2022Contraction of Locally Differentially Private Mechanismscited by 8
  7. 2023Communication Efficient Private Federated Learning Using Ditheringcited by 8
  8. 2024Universal Exact Compression of Differentially Private Mechanismscited by 8
  9. 2022Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Designcited by 6
  10. 2023Adaptive Compression in Federated Learning via Side Informationcited by 6
  11. 2024Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacycited by 4
  12. 2024Some Notes on the Sample Complexity of Approximate Channel Simulationcited by 4
10 more
  1. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  2. 2023Breaking the Communication-Privacy-Accuracy Tradeoff with f-Differential Privacycited by 3
  3. 2024Locally Private Sampling with Public Datacited by 3
  4. 2026Scalable Differentially Private Data Compression via Diffusion and Stochastic Codescited by 3
  5. 2025Communication-Efficient and Privacy-Adaptable Mechanism for Federated Learningcited by 2
  6. 2024Beyond Statistical Estimation: Differentially Private Individual Computation via Shufflingcited by 1
  7. 2026Communication-Efficient and Privacy-Adaptable Mechanism -- a Federated Learning Scheme with Convergence Analysiscited by 1
  8. 2026Deep Randomized Distributed Function Computation (DeepRDFC): Neural Distributed Channel Simulationcited by 1
  9. 2026Secure Rate-Distortion-Perception: A Randomized Distributed Function Computation Approach for Realismcited by 0
  10. 2026Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacycited by 0