Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915520240943104 |
|---|---|
| author | Yoon, Sun-Moon Park, Hyun-Young Nam, Seung-Hyun Lee, Si-Hyeon |
| author_facet | Yoon, Sun-Moon Park, Hyun-Young Nam, Seung-Hyun Lee, Si-Hyeon |
| contents | We study the problem of discrete distribution estimation under utility-optimized local differential privacy (ULDP), which enforces local differential privacy (LDP) on sensitive data while allowing more accurate inference on non-sensitive data. In this setting, we completely characterize the fundamental privacy-utility trade-off. The converse proof builds on several key ideas, including a generalized uniform asymptotic Cramér-Rao lower bound, a reduction showing that it suffices to consider a newly defined class of extremal ULDP mechanisms, and a novel distribution decomposition technique tailored to ULDP constraints. For the achievability, we propose a class of utility-optimized block design (uBD) schemes, obtained as nontrivial modifications of the block design mechanism known to be optimal under standard LDP constraints, while incorporating the distribution decomposition idea used in the converse proof and a score-based linear estimator. These results provide a tight characterization of the estimation accuracy achievable under ULDP and reveal new insights into the structure of optimal mechanisms for privacy-preserving statistical inference. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24173 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy Yoon, Sun-Moon Park, Hyun-Young Nam, Seung-Hyun Lee, Si-Hyeon Cryptography and Security Information Theory We study the problem of discrete distribution estimation under utility-optimized local differential privacy (ULDP), which enforces local differential privacy (LDP) on sensitive data while allowing more accurate inference on non-sensitive data. In this setting, we completely characterize the fundamental privacy-utility trade-off. The converse proof builds on several key ideas, including a generalized uniform asymptotic Cramér-Rao lower bound, a reduction showing that it suffices to consider a newly defined class of extremal ULDP mechanisms, and a novel distribution decomposition technique tailored to ULDP constraints. For the achievability, we propose a class of utility-optimized block design (uBD) schemes, obtained as nontrivial modifications of the block design mechanism known to be optimal under standard LDP constraints, while incorporating the distribution decomposition idea used in the converse proof and a score-based linear estimator. These results provide a tight characterization of the estimation accuracy achievable under ULDP and reveal new insights into the structure of optimal mechanisms for privacy-preserving statistical inference. |
| title | Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy |
| topic | Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2509.24173 |