# Mean Estimation Under Heterogeneous Privacy Demands

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 65 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 30 of 34)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [Heterogeneous Differential Privacy](https://mlsanity.com/paper/1504.06998/) (2015)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Private Query Release Assisted by Public Data](https://mlsanity.com/paper/2004.10941/) (2020)
- [A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis](https://mlsanity.com/paper/2010.05253/) (2020)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation](https://mlsanity.com/paper/1305.6000/) (2013)
- [Learning from Mixtures of Private and Public Populations](https://mlsanity.com/paper/2008.00331/) (2020)
- [Privately Answering Classification Queries in the Agnostic PAC Model](https://mlsanity.com/paper/1907.13553/) (2019)
- [BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model](https://mlsanity.com/paper/1705.00831/) (2017)
- [Optimal Data Acquisition with Privacy-Aware Agents](https://mlsanity.com/paper/2209.06340/) (2022)
- [Reviewing and Improving the Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/1911.12060/) (2019)
- [One-sided Differential Privacy](https://mlsanity.com/paper/1712.05888/) (2017)
- [Combining Public and Private Data](https://mlsanity.com/paper/2111.00115/) (2021)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)

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

- [Private Estimation when Data and Privacy Demands are Correlated](https://mlsanity.com/paper/2407.11274/) (2024)
- [Managing Correlations in Data and Privacy Demand](https://mlsanity.com/paper/2509.02856/) (2025)
- [Robust Estimation Under Heterogeneous Corruption Rates](https://mlsanity.com/paper/2508.15051/) (2025)
- [High-Probability Bounds For Heterogeneous Local Differential Privacy](https://mlsanity.com/paper/2510.11895/) (2025)
- [Limits of Personalizing Differential Privacy Budgets](https://mlsanity.com/paper/2605.13503/) (2026)
- [Performative Privacy: When Differential Privacy Maximizes Utility](https://mlsanity.com/paper/2608.28198/) (2026)

## Abstract (arXiv)

Differential Privacy (DP) is a well-established framework to quantify privacy loss incurred by any algorithm. Traditional formulations impose a uniform privacy requirement for all users, which is often inconsistent with real-world scenarios in which users dictate their privacy preferences individually. This work considers the problem of mean estimation, where each user can impose their own distinct privacy level. The algorithm we propose is shown to be minimax optimal and has a near-linear run-time. Our results elicit an interesting saturation phenomenon that occurs. Namely, the privacy requirements of the most stringent users dictate the overall error rates. As a consequence, users with less but differing privacy requirements are all given more privacy than they require, in equal amounts. In other words, these privacy-indifferent users are given a nontrivial degree of privacy for free, without any sacrifice in the performance of the estimator.