# Managing Correlations in Data and Privacy Demand

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 64 references that are in the map.
- First posted on arXiv 2 Sep 2025.

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

- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [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)
- [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)
- [SoK: Differential Privacies](https://mlsanity.com/paper/1906.01337/) (2019)
- [Heterogeneous Differential Privacy](https://mlsanity.com/paper/1504.06998/) (2015)
- [Private Query Release Assisted by Public Data](https://mlsanity.com/paper/2004.10941/) (2020)
- [One Parameter Defense -- Defending against Data Inference Attacks via Differential Privacy](https://mlsanity.com/paper/2203.06580/) (2022)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [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)
- [Combining Public and Private Data](https://mlsanity.com/paper/2111.00115/) (2021)
- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [Correlated Data in Differential Privacy: Definition and Analysis](https://mlsanity.com/paper/2008.00180/) (2020)
- [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)
- [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)
- [Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy](https://mlsanity.com/paper/2410.18404/) (2024)
- [Privacy-Aware Data Acquisition under Data Similarity in Regression Markets](https://mlsanity.com/paper/2312.02611/) (2023)
- [Equilibria of Data Marketplaces with Privacy-Aware Sellers under Endogenous Privacy Costs](https://mlsanity.com/paper/2402.08826/) (2024)

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

- [Integrating Feature Correlation in Differential Privacy with Applications in DP-ERM](https://mlsanity.com/paper/2605.03945/) (2026)
- [Limits of Personalizing Differential Privacy Budgets](https://mlsanity.com/paper/2605.13503/) (2026)

## Abstract (arXiv)

Previous works in the differential privacy literature that allow users to choose their privacy levels typically operate under the heterogeneous differential privacy (HDP) framework with the simplifying assumption that user data and privacy levels are not correlated. Firstly, we demonstrate that the standard HDP framework falls short when user data and privacy demands are allowed to be correlated. Secondly, to address this shortcoming, we propose an alternate framework, Add-remove Heterogeneous Differential Privacy (AHDP), that jointly accounts for user data and privacy preference. We show that AHDP is robust to possible correlations between data and privacy. Thirdly, we formalize the guarantees of the proposed AHDP framework through an operational hypothesis testing perspective. The hypothesis testing setup may be of independent interest in analyzing other privacy frameworks as well. Fourthly, we show that there exists non-trivial AHDP mechanisms that notably do not require prior knowledge of the data-privacy correlations. We propose some such mechanisms and apply them to core statistical tasks such as mean estimation, frequency estimation, and linear regression. The proposed mechanisms are simple to implement with minimal assumptions and modeling requirements, making them attractive for real-world use. Finally, we empirically evaluate proposed AHDP mechanisms, highlighting their trade-offs using LLM-generated synthetic datasets, which we release for future research.