# Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 47 references that are in the map.
- First posted on arXiv 27 Apr 2023.

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

- [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)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [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)
- [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)
- [The Power of The Hybrid Model for Mean Estimation](https://mlsanity.com/paper/1811.12040/) (2018)
- [One-sided Differential Privacy](https://mlsanity.com/paper/1712.05888/) (2017)
- [Combining Public and Private Data](https://mlsanity.com/paper/2111.00115/) (2021)
- [The power of synergy in differential privacy: Combining a small curator with local randomizers](https://mlsanity.com/paper/1912.08951/) (2019)
- [Probabilistic Matrix Factorization with Personalized Differential Privacy](https://mlsanity.com/paper/1810.08509/) (2018)
- [Heterogeneous Differential Privacy via Graphs](https://mlsanity.com/paper/2203.15429/) (2022)

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

- [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)
- [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)
- [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)

## Abstract (arXiv)

Differential Privacy (DP) is a well-established framework to quantify privacy loss incurred by any algorithm. Traditional DP 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 under heterogeneous DP constraints, where each user can impose their own distinct privacy level. The algorithm we propose is shown to be minimax optimal when there are two groups of users with distinct privacy levels. Our results elicit an interesting saturation phenomenon that occurs as one group's privacy level is relaxed, while the other group's privacy level remains constant. Namely, after a certain point, further relaxing the privacy requirement of the former group does not improve the performance of the minimax optimal mean estimator. Thus, the central server can offer a certain degree of privacy without any sacrifice in performance.