# Optimal Algorithms for Mean Estimation under Local Differential Privacy

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

## Key facts

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

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

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [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)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [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)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs](https://mlsanity.com/paper/2008.07180/) (2020)
- [The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation](https://mlsanity.com/paper/2009.08000/) (2020)
- [Asymptotically optimal private estimation under mean square loss](https://mlsanity.com/paper/1708.00059/) (2017)

## Built on by (most cited first, 30 of 36)

- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy](https://mlsanity.com/paper/2405.13453/) (2024)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Optimal Differentially Private Model Training with Public Data](https://mlsanity.com/paper/2306.15056/) (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)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- ["You Can't Fix What You Can't Measure": Privately Measuring Demographic Performance Disparities in Federated Learning](https://mlsanity.com/paper/2206.12183/) (2022)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [Multi-Message Shuffled Privacy in Federated Learning](https://mlsanity.com/paper/2302.11152/) (2023)
- [Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacy](https://mlsanity.com/paper/2303.00035/) (2023)
- [Provable Mutual Benefits from Federated Learning in Privacy-Sensitive Domains](https://mlsanity.com/paper/2403.06672/) (2024)
- [Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks](https://mlsanity.com/paper/2406.03766/) (2024)
- [Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy](https://mlsanity.com/paper/2410.18404/) (2024)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [Differentially Private Multimodal Laplacian Dropout (DP-MLD) for EEG Representative Learning](https://mlsanity.com/paper/2409.13440/) (2024)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Accelerating Differentially Private Federated Learning via Adaptive Extrapolation](https://mlsanity.com/paper/2504.09850/) (2025)
- [High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inference](https://mlsanity.com/paper/2508.05212/) (2025)
- [BinaryShield: Cross-Service Threat Intelligence in LLM Services using Privacy-Preserving Fingerprints](https://mlsanity.com/paper/2509.05608/) (2025)
- [Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions](https://mlsanity.com/paper/2312.07055/) (2023)

## 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.