Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
This work addresses privacy-preserving data analysis for datasets with discrete distributions, offering incremental improvements over existing methods.
The authors tackled the problem of generating a differentially private sample from a discrete distribution by introducing the reveal-or-obscure (ROO) algorithm, which improves upon prior bounds, and a data-specific variant (DS-ROO) that adaptively adjusts parameters to achieve better utility under the same privacy budget.
We introduce a differentially private (DP) algorithm called reveal-or-obscure (ROO) to generate a single representative sample from a dataset of $n$ observations drawn i.i.d. from an unknown discrete distribution $P$. Unlike methods that add explicit noise to the estimated empirical distribution, ROO achieves $ε$-differential privacy by randomly choosing whether to "reveal" or "obscure" the empirical distribution. While ROO is structurally identical to Algorithm 1 proposed by Cheu and Nayak (arXiv:2412.10512), we prove a strictly better bound on the sampling complexity than that established in Theorem 12 of (arXiv:2412.10512). To further improve the privacy-utility trade-off, we propose a novel generalized sampling algorithm called Data-Specific ROO (DS-ROO), where the probability of obscuring the empirical distribution of the dataset is chosen adaptively. We prove that DS-ROO satisfies $ε$-DP, and provide empirical evidence that DS-ROO can achieve better utility under the same privacy budget of vanilla ROO.