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

• URL: http://arxiv.org/abs/2504.14696v1
• Date: Sun, 20 Apr 2025 18:20:11 GMT
• Title: Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
• Authors: Naima Tasnim, Atefeh Gilani, Lalitha Sankar, Oliver Kosut,
• Abstract summary: We introduce a differentially private (DP) algorithm called reveal-or-obscure (ROO)<n>ROO achieves $epsilon$-differential privacy by randomly choosing whether to "reveal" or "obscure" the empirical distribution.<n>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.
• Score: 12.149550080095919
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\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 (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 $\epsilon$-DP, and provide empirical evidence that DS-ROO can achieve better utility under the same privacy budget of vanilla ROO.

Related papers

• Differentially Private Multi-Sampling from Distributions [4.292685318253575]
  We study the sample complexity of DP emphsingle-sampling i.e., the minimum number of samples needed to perform this task. We define two variants of emphmulti-sampling, where the goal is to privately approximate $m>1$ samples.
  arXiv  Detail & Related papers  (2024-12-13T19:14:05Z)
• Statistical Inference for Privatized Data with Unknown Sample Size [7.933465724913661]
  We develop both theory and algorithms to analyze privatized data in the unbounded differential privacy(DP) We show that the distance between the sampling distributions under unbounded DP and bounded DP goes to zero as the sample size $n$ goes to infinity.
  arXiv  Detail & Related papers  (2024-06-10T13:03:20Z)
• Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy [23.12198546384976]
  Posterior sampling provides $varepsilon$-pure differential privacy guarantees. It does not suffer from potentially unbounded privacy breach introduced by $(varepsilon,delta)$-approximate DP. In practice, however, one needs to apply approximate sampling methods such as Markov chain Monte Carlo.
  arXiv  Detail & Related papers  (2023-10-23T07:54:39Z)
• Policy Evaluation in Distributional LQR [70.63903506291383]
  We provide a closed-form expression of the distribution of the random return. We show that this distribution can be approximated by a finite number of random variables. Using the approximate return distribution, we propose a zeroth-order policy gradient algorithm for risk-averse LQR.
  arXiv  Detail & Related papers  (2023-03-23T20:27:40Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Differentially Private Sampling from Distributions [1.452875650827562]
  In some regimes, private sampling requires fewer observations than learning a description of $P$ nonprivately. For some classes of distributions, the overhead in the number of observations needed for private learning compared to non-private learning is completely captured by the number of observations needed for private sampling.
  arXiv  Detail & Related papers  (2022-11-15T14:56:42Z)
• Differential Privacy of Dirichlet Posterior Sampling [0.0]
  We study the inherent privacy of releasing a single draw from a Dirichlet posterior distribution. With the notion of truncated concentrated differential privacy (tCDP), we are able to derive a simple privacy guarantee of the Dirichlet posterior sampling.
  arXiv  Detail & Related papers  (2021-10-03T07:41:19Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  We formulate a method that learns a finite set of statistics from each return distribution via neural networks. Our method can be interpreted as implicitly matching all orders of moments between a return distribution and its Bellman target. Experiments on the suite of Atari games show that our method outperforms the standard distributional RL baselines.
  arXiv  Detail & Related papers  (2020-07-24T05:18:17Z)
• RDP-GAN: A R\'enyi-Differential Privacy based Generative Adversarial Network [75.81653258081435]
  Generative adversarial network (GAN) has attracted increasing attention recently owing to its impressive ability to generate realistic samples with high privacy protection. However, when GANs are applied on sensitive or private training examples, such as medical or financial records, it is still probable to divulge individuals' sensitive and private information. We propose a R'enyi-differentially private-GAN (RDP-GAN), which achieves differential privacy (DP) in a GAN by carefully adding random noises on the value of the loss function during training.
  arXiv  Detail & Related papers  (2020-07-04T09:51:02Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.