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

Naima Tasnim, Atefeh Gilani, Lalitha Sankar and Oliver Kosut · 2025

Read Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions by Naima Tasnim, Atefeh Gilani, Lalitha Sankar and Oliver Kosut (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14696.txt.

Introduction

Sharing one fair sample from private data sounds simple, yet noise-adding methods waste much of the signal. Naima Tasnim, Atefeh Gilani, Lalitha Sankar, and Oliver Kosut propose a coin-flip style method in a 2025 paper. Their algorithm either shows the data's own spread or hides it behind a decoy spread. That random choice alone yields a formal privacy guarantee.

The method matches an earlier design but with a tighter proof of how much data it needs. A smarter variant sets the hiding chance from the data itself. Tests show the variant buys better accuracy at the same privacy budget. The authors frame both for discrete data like counts and categories.

Catalog record

CREATORNaima Tasnim, Atefeh Gilani, Lalitha Sankar and Oliver Kosut
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-14696

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions Naima Tasnim, Atefeh Gilani, Lalitha Sankar and Oliver Kosut Abstract We introduce a differentially private (DP) algorithm called reveal-or-obscure (ROO) to generate a single representative sample from a dataset of n n observations drawn i.i.d. from an unknown discrete distribution P P . Unlike methods that add explicit noise to the estimated empirical distribution, ROO achieves ϵ \epsilon -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 [ 1 ] , we prove a strictly better bound on the sampling complexity than that extablished in Theorem 12 of [ 1 ] . 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 ϵ \epsilon -DP, and provide empirical evidence that DS-ROO can achieve better utility under the same privacy budget of vanilla ROO. I Introduction The widespread use of sensitive data across various domains, including healthcare, finance, law enforcement, and social sciences, has heightened the importance of privacy-preserving data analysis. Consequently, there is a growing need for mechanisms that allow data analysis while minimizing individual privacy risks. One promising approach is the use of synthetic data that capture the statistical properties of the original data. Differential Privacy (DP) [ 2 , 3 ] has emerged as a sound framework for formalizing privacy guarantees across a range of applications, including data analysis. In essence, DP ensures that the output of an algorithm does not differ by much whether or not an individual’s data is included in the input. The task of synthetic data generation is closely related to the broader problem of learning probability distributions [ 4 ] . In the non-private setting, a learning algorithm approximates a distribution from which one can sample new data points that are representative of the original data. When privacy constraints are introduced, learning a distribution becomes significantly more challenging. In many practical cases, it may be sufficient to produce a small number of representative samples instead. The task of privately releasing one sample—known as DP sampling—is easier than full-fledged learning, since it requires less information from the underlying distribution. Motivated by this, we propose a novel DP sampling algorithm for discrete distributions on a finite alphabet. The key idea of our approach is to “obscure” the empirical distribution of the input dataset with a certain probability, or “reveal” it otherwise. Hence, we call our proposed algorithm reveal-or-obscure (ROO). Main Contributions. Our main contributions are: • We propose ROO—a sampling algorithm that achieves differential privacy without explicitly perturbing the empirical distribution of the input dataset. We incorporate uncertainty in our algorithm by sampling from the uniform distribution with some fixed probability q . • We prove that our proposed algorithm reduces the sampling complexity while achieving better privacy-utility trade-off than the state-of-the art [ 5 ] , [ 1 ] . • We also propose DS-ROO (data-specific ROO) as a technique to generalize ROO by making q , i.e., the probability of sampling from the uniform distribution, a function of the empirical distribution of the dataset. We prove that it is possible to achieve the same privacy guarantee with a lower q value relative to the vanilla ROO algorithm for sufficiently large datasets. • We demonstrate empirically that, for the same privacy guarantee, DS-ROO achieves better utility than vanilla ROO as well as the state-of-the-art in [ 5 ] . Related Work. The problem of differentially private sampling from unknown distributions is first investigated in [ 5 ] . Raskhodnikova et al. [ 5 ] provide the first known bounds with (\epsilon,\delta) -DP guarantees on the complexity of sampling from arbitrary distributions over a discrete alphabet. DP algorithms for sampling from higher dimensional distributions such as multivariate Gaussians are presented in [ 6 ] . Husain et al. [ 7 ] considers DP sampling in the local setting, where the central aggregator cannot be trusted and each user must produce a single data record privately. Private sampling has also been studied in the distributed setting [ 8 , 9 ] . A key focus of these efforts has been to reduce the sample complexity of DP-assured private sampling. While a recent and concurrent work [ 1 ] independent from ours proposes an algorithm structurally identical to ROO, our analysis establishes a strictly better sampling complexity bound in the same setting. More generally, the problem of releasing a dataset in a differentially private manner has also been studied; for example, see [ 10 , 11 , 12 , 13 , 14 ] . Generating a single sample in a private manner is the first step towards releasing a larger synthetic dataset, and to this end, we focus on the former challenge in this paper. II Problem Setup We begin by briefly reviewing some relevant definitions. We use uppercase letters, e.g., X , to denote random variables (RVs), and lowercase letters, e.g. x , for their instantiations. We assume that the dataset consists of n RVs sampled from a finite alphabet of k letters; without loss of generality, we take this alphabet to be [k]=\{1,2,\dots,k\} . Let \mathcal{P} be the class of probability distributions on [k] . Given a dataset X^{n}=(X_{1},X_{2},\dots,X_{n}) of n i.i.d. observations from some unknown P\in\mathcal{P} , a randomized algorithm (privacy mechanism) \mathcal{A}:\mathcal{X}^{n}\mapsto\mathcal{X} outputs a single sample from \mathcal{X} . Let Y=\mathcal{A}(X^{n}) be the random variable corresponding to the output of algorithm \mathcal{A} given input X^{n} . The output \mathcal{A}(X^{n}) is drawn from a distribution Q such that \displaystyle Q(y)=\sum_{x^{n}\in\mathcal{X}^{n}}\Pr\left\{\mathcal{A}(x^{n})=y|x^{n}\right\}\Pr\left\{X^{n}=x^{n}\right\}. (1) The accuracy of \mathcal{A} is measured by the closeness between Q and P . We use the total variation distance , defined as \displaystyle d_{TV}(Q,P)=\frac{1}{2}\|Q-P\|_{1}=\frac{1}{2}\sum_{x}|Q(x)-P(x)|. (2) We use the following definition of sampling accuracy, introduced in [ 15 ] . Definition 1 (Accuracy of Sampling [ 15 ] ) An algorithm \mathcal{A} is \alpha -accurate on a distribution P if the total variation distance, d_{TV} between Q and P is bounded by some constant \alpha , i.e., \displaystyle d_{TV}(Q,P)\leq\alpha. (3) An algorithm is \alpha -accurate on a class \mathcal{P} of distributions if it is \alpha -accurate on every P\in\mathcal{P} . Two datasets x^{n} and \tilde{x}^{n} are considered neighbors , denoted x^{n}\sim\tilde{x}^{n} , if they differ by at most one entry. DP is defined with respect to all such neighboring datasets as follows. Definition 2 (Differential Privacy [ 2 ] ) A randomized algorithm, or mechanism \mathcal{A}:\mathcal{X}^{n}\to\mathcal{Y} is considered \epsilon -differentially private ( \epsilon -DP) if, for every pair of neighboring datasets x^{n}\sim\tilde{x}^{n}\in\mathcal{X}^{n} , and for all Y\subseteq\mathcal{Y} , \displaystyle\Pr\{\mathcal{A}(x^{n})\in Y\}\leq e^{\epsilon}\Pr\{\mathcal{A}(\tilde{x}^{n})\in Y\}. (4) In [ 5 ] , the authors present an achievable \epsilon -DP sampler which does the following: (i) computes, for each j\in[k] , the empirical probability distribution \hat{p}_{j} , (ii) adds Laplace noise to each count, (iii) uses an L_{1} projection to restrict the Laplace-noised distribution to be a probability vector \tilde{P}=(\tilde{p}_{1},\dots,\tilde{p}_{k}) , and (iv) outputs an element of [k] sampled from the distribution \tilde{P} . For this algorithm, they show that for a sampling complexity \displaystyle n^{\prime}=\frac{2k}{\alpha\epsilon},

Read the complete text