# Utility-Optimized Local Differential Privacy Mechanisms for Distribution Estimation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2018.

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

- [Differential Privacy for Text Analytics via Natural Text Sanitization](https://mlsanity.com/paper/2106.01221/) (2021)
- [A Customized Text Sanitization Mechanism with Differential Privacy](https://mlsanity.com/paper/2207.01193/) (2022)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [When Alignment Fails: Multimodal Adversarial Attacks on Vision-Language-Action Models](https://mlsanity.com/paper/2511.16203/) (2025)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Fine-grained Poisoning Attack to Local Differential Privacy Protocols for Mean and Variance Estimation](https://mlsanity.com/paper/2205.11782/) (2022)
- [Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems](https://mlsanity.com/paper/2306.13054/) (2023)
- [When Fairness Meets Privacy: Fair Classification with Semi-Private Sensitive Attributes](https://mlsanity.com/paper/2207.08336/) (2022)
- [Task-aware Privacy Preservation for Multi-dimensional Data](https://mlsanity.com/paper/2110.02329/) (2021)
- [Decouple-and-Sample: Protecting sensitive information in task agnostic data release](https://mlsanity.com/paper/2203.13204/) (2022)
- [Privacy-Utility Tradeoffs in Quantum Information Processing](https://mlsanity.com/paper/2602.10510/) (2026)
- [Feature-Aware Anisotropic Local Differential Privacy for Utility-Preserving Graph Representation Learning in Metal Additive Manufacturing](https://mlsanity.com/paper/2604.05077/) (2026)

## Abstract (arXiv)

LDP (Local Differential Privacy) has been widely studied to estimate statistics of personal data (e.g., distribution underlying the data) while protecting users' privacy. Although LDP does not require a trusted third party, it regards all personal data equally sensitive, which causes excessive obfuscation hence the loss of utility. In this paper, we introduce the notion of ULDP (Utility-optimized LDP), which provides a privacy guarantee equivalent to LDP only for sensitive data. We first consider the setting where all users use the same obfuscation mechanism, and propose two mechanisms providing ULDP: utility-optimized randomized response and utility-optimized RAPPOR. We then consider the setting where the distinction between sensitive and non-sensitive data can be different from user to user. For this setting, we propose a personalized ULDP mechanism with semantic tags to estimate the distribution of personal data with high utility while keeping secret what is sensitive for each user. We show theoretically and experimentally that our mechanisms provide much higher utility than the existing LDP mechanisms when there are a lot of non-sensitive data. We also show that when most of the data are non-sensitive, our mechanisms even provide almost the same utility as non-private mechanisms in the low privacy regime.