mlsanityData to 7 Oct 2026

Optimal Algorithms for Mean Estimation under Local Differential Privacy

arXiv 2205.02466 ↗First posted 5 May 2022cs.LG cs.CRcited by 36

Not on the map. Why?

Abstract (arXiv)

We study the problem of mean estimation of ℓ2-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the asymptotically optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the protocol with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of locally private randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). Builds on 16 of its 32 references that are in the map. First posted on arXiv 5 May 2022.

Builds on

16 of 32 references.

References · 16

  1. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  2. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  3. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 157
  4. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 127
  5. 2018Distributed Differential Privacy via Shufflingcited by 115
  6. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  7. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  8. 2019The Privacy Blanket of the Shuffle Modelcited by 73
  9. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  10. 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
  11. 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
  12. 2017Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacycited by 28
4 more
  1. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  2. 2020Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offscited by 15
  3. 2020The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimationcited by 7
  4. 2017Asymptotically optimal private estimation under mean square losscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 9; 2024: 13; 2025: 4; 2026: 6.

36 papers.

Sort:

  1. 2022Almost Tight Error Bounds on Differentially Private Continual Countingcited by 25
  2. 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
  3. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  4. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  5. 2023Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimationcited by 9
  6. 2023Optimal Differentially Private Model Training with Public Datacited by 9
  7. 2022Contraction of Locally Differentially Private Mechanismscited 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. 2023Private Federated Learning with Autotuned Compressioncited by 5
  11. 2024Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messagescited by 5
  12. 2024Exactly Minimax-Optimal Locally Differentially Private Samplingcited by 5
24 more
  1. 2024Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacycited by 4
  2. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  3. 2022"You Can't Fix What You Can't Measure": Privately Measuring Demographic Performance Disparities in Federated Learningcited by 3
  4. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  5. 2024Learning with User-Level Local Differential Privacycited by 3
  6. 2023Multi-Message Shuffled Privacy in Federated Learningcited by 2
  7. 2023Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacycited by 2
  8. 2024Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networkscited by 2
  9. 2024Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacycited by 2
  10. 2026How Much is Left? LLMs Linearly Encode Their Remaining Output Lengthcited by 2
  11. 2024Provable Mutual Benefits from Federated Learning in Privacy-Sensitive Domainscited by 1
  12. 2024Beyond Statistical Estimation: Differentially Private Individual Computation via Shufflingcited by 1
  13. 2024Differentially Private Multimodal Laplacian Dropout (DP-MLD) for EEG Representative Learningcited by 1
  14. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  15. 2025Accelerating Differentially Private Federated Learning via Adaptive Extrapolationcited by 1
  16. 2025High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inferencecited by 1
  17. 2025BinaryShield: Cross-Service Threat Intelligence in LLM Services using Privacy-Preserving Fingerprintscited by 1
  18. 2023Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functionscited by 0
  19. 2024Differential Privacy on Trust Graphscited by 0
  20. 2026Shuffling-Aware Optimization for Private Vector Mean Estimationcited by 0
  21. 2026Differentially Private Sampling from Distributions via Wasserstein Projectioncited by 0
  22. 2026Jacobian-Guided Anisotropic Noise Reshaping for Enhancing Representation Utility under Local Differential Privacycited by 0
  23. 2026Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Costcited by 0
  24. 2026SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuantcited by 0