# Private Estimation when Data and Privacy Demands are Correlated

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 15 Jul 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [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)
- [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)
- [Optimal Data Acquisition with Privacy-Aware Agents](https://mlsanity.com/paper/2209.06340/) (2022)
- [Large Deviation Methods for Approximate Probabilistic Inference](https://mlsanity.com/paper/1301.7392/) (2013)
- [Combining Public and Private Data](https://mlsanity.com/paper/2111.00115/) (2021)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free](https://mlsanity.com/paper/2305.09668/) (2023)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)
- [The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning](https://mlsanity.com/paper/2301.13336/) (2023)
- [Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine](https://mlsanity.com/paper/2309.06068/) (2023)
- [Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression](https://mlsanity.com/paper/2309.10340/) (2023)
- [Personalized Differential Privacy for Ridge Regression](https://mlsanity.com/paper/2401.17127/) (2024)

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

- [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)

## Abstract (arXiv)

Differential Privacy (DP) is the current gold-standard for ensuring privacy for statistical queries. Estimation problems under DP constraints appearing in the literature have largely focused on providing equal privacy to all users. We consider the problems of empirical mean estimation for univariate data and frequency estimation for categorical data, both subject to heterogeneous privacy constraints. Each user, contributing a sample to the dataset, is allowed to have a different privacy demand. The dataset itself is assumed to be worst-case and we study both problems under two different formulations -- first, where privacy demands and data may be correlated, and second, where correlations are weakened by random permutation of the dataset. We establish theoretical performance guarantees for our proposed algorithms, under both PAC error and mean-squared error. These performance guarantees translate to minimax optimality in several instances, and experiments confirm superior performance of our algorithms over other baseline techniques.