mlsanityData to 7 Oct 2026

Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation

arXiv 2304.01541 ↗First posted 4 Apr 2023stat.ML cs.CR cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA). We study the optimal accuracy of mean and frequency estimation (canonical models for FL and FA respectively) under joint communication and (varepsilon, δ)-differential privacy (DP) constraints. We show that in order to achieve the optimal error under (varepsilon, δ)-DP, it is sufficient for each client to send Thetaleft( n minleft(varepsilon, varepsilon2right)right) bits for FL and Thetaleft(logleft( nminleft(varepsilon, varepsilon2right) right)right) bits for FA to the server, where n is the number of participating clients. Without compression, each client needs O(d) bits and log d bits for the mean and frequency estimation problems respectively (where d corresponds to the number of trainable parameters in FL or the domain size in FA), which means that we can get significant savings in the regime n minleft(varepsilon, varepsilon2right) = o(d), which is often the relevant regime in practice. Our algorithms leverage compression for privacy amplification: when each client communicates only partial information about its sample, we show that privacy can be amplified by randomly selecting the part contributed by each client.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 57 of its 88 references that are in the map. First posted on arXiv 4 Apr 2023.

Builds on

57 of 88 references.

References · 57

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Deep Learning with Differential Privacycited by 2,682
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  6. 2017Renyi Differential Privacycited by 643
  7. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  8. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  9. 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 237
  10. 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 216
  11. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
  12. 2016Practical Secure Aggregation for Federated Learning on User-Held Datacited by 178
38 more
  1. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  2. 2018Expanding the Reach of Federated Learning by Reducing Client Resource Requirementscited by 162
  3. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 157
  4. 2014A* Samplingcited by 150
  5. 2016Distributed Mean Estimation with Limited Communicationcited by 134
  6. 2020The Discrete Gaussian for Differential Privacycited by 134
  7. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 127
  8. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 127
  9. 2018Distributed Differential Privacy via Shufflingcited by 115
  10. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  11. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  12. 2021The Skellam Mechanism for Differentially Private Federated Learningcited by 66
  13. 2016Discrete Distribution Estimation under Local Privacycited by 58
  14. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  15. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  16. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  17. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  18. 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
  19. 2015Local, Private, Efficient Protocols for Succinct Histogramscited by 35
  20. 2018Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraintscited by 33
  21. 2019Federated Heavy Hitters Discovery with Differential Privacycited by 32
  22. 2018Inference under Information Constraints I: Lower Bounds from Chi-Square Contractioncited by 31
  23. 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacycited by 29
  24. 2017Practical Locally Private Heavy Hitterscited by 28
  25. 2020rTop-k: A Statistical Estimation Approach to Distributed SGDcited by 27
  26. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  27. 2018Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communicationcited by 26
  28. 2016Collecting and Analyzing Data from Smart Device Users with Local Differential Privacycited by 25
  29. 2020Federated Learning with Sparsification-Amplified Privacy and Adaptive Optimizationcited by 25
  30. 2019Inference under Information Constraints II: Communication Constraints and Shared Randomnesscited by 22
  31. 2020Fisher information under local differential privacycited by 22
  32. 2021Optimal Compression of Locally Differentially Private Mechanismscited by 22
  33. 2017Heavy Hitters and the Structure of Local Privacycited by 20
  34. 2019Separating Local & Shuffled Differential Privacy via Histogramscited by 16
  35. 2021Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overheadcited by 16
  36. 2019Communication Complexity in Locally Private Distribution Estimation and Heavy Hitterscited by 11
  37. 2022Private Frequency Estimation via Projective Geometrycited by 9
  38. 2017Differential Privacy on Finite Computerscited by 8

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 10; 2025: 5; 2026: 6.

22 papers.

Sort:

  1. 2024Advances and Open Challenges in Federated Foundation Modelscited by 33
  2. 2025Privacy amplification by random allocationcited by 13
  3. 2023Compression with Exact Error Distribution for Federated Learningcited by 9
  4. 2024Universal Exact Compression of Differentially Private Mechanismscited by 8
  5. 2025Leveraging Randomness in Model and Data Partitioning for Privacy Amplificationcited by 7
  6. 2024Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messagescited by 5
  7. 2024Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacycited by 4
  8. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  9. 2024Learning with User-Level Local Differential Privacycited by 3
  10. 2026Efficient privacy loss accounting for subsampling and random allocationcited by 3
  11. 2024TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Datacited by 2
  12. 2024Privacy Amplification for the Gaussian Mechanism via Bounded Supportcited by 2
10 more
  1. 2024Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacycited by 1
  2. 2024CorBin-FL: A Differentially Private Federated Learning Mechanism using Common Randomnesscited by 1
  3. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  4. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  5. 2026Analysis of Shuffling Beyond Pure Local Differential Privacycited by 1
  6. 2025FedRP: A Communication-Efficient Approach for Differentially Private Federated Learning Using Random Projectioncited by 0
  7. 2026Differentially Private and Communication Efficient Large Language Model Split Inference via Stochastic Quantization and Soft Promptcited by 0
  8. 2026Shuffling-Aware Optimization for Private Vector Mean Estimationcited by 0
  9. 2026SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuantcited by 0
  10. 2026Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacycited by 0