# Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 20 Apr 2025.

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

- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Private sampling: a noiseless approach for generating differentially private synthetic data](https://mlsanity.com/paper/2109.14839/) (2021)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)
- [Sample Amplification: Increasing Dataset Size even when Learning is Impossible](https://mlsanity.com/paper/1904.12053/) (2019)
- [On Differentially Private Sampling from Gaussian and Product Distributions](https://mlsanity.com/paper/2306.12549/) (2023)
- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Differentially Private Multi-Sampling from Distributions](https://mlsanity.com/paper/2412.10512/) (2024)

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

- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)

## Abstract (arXiv)

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.