Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy
It provides a complete theoretical solution for distribution estimation under a privacy model that balances utility for non-sensitive data with LDP protection, which is important for privacy-preserving data analysis.
This paper characterizes the fundamental privacy-utility trade-off for discrete distribution estimation under utility-optimized local differential privacy (ULDP), providing a tight lower bound and an optimal mechanism (uBD scheme) that achieves it.
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.