# Differentially Private Multi-Sampling from Distributions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 16 references that are in the map.
- First posted on arXiv 13 Dec 2024.

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

- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)
- [On Differentially Private Sampling from Gaussian and Product Distributions](https://mlsanity.com/paper/2306.12549/) (2023)
- [Privately Answering Counting Queries with Generalized Gaussian Mechanisms](https://mlsanity.com/paper/2010.01457/) (2020)

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

- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)
- [Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions](https://mlsanity.com/paper/2504.14696/) (2025)

## Abstract (arXiv)

Many algorithms have been developed to estimate probability distributions subject to differential privacy (DP): such an algorithm takes as input independent samples from a distribution and estimates the density function in a way that is insensitive to any one sample. A recent line of work, initiated by Raskhodnikova et al. (Neurips '21), explores a weaker objective: a differentially private algorithm that approximates a single sample from the distribution. Raskhodnikova et al. studied the sample complexity of DP single-sampling i.e., the minimum number of samples needed to perform this task. They showed that the sample complexity of DP single-sampling is less than the sample complexity of DP learning for certain distribution classes. We define two variants of multi-sampling, where the goal is to privately approximate m>1 samples. This better models the realistic scenario where synthetic data is needed for exploratory data analysis. A baseline solution to multi-sampling is to invoke a single-sampling algorithm m times on independently drawn datasets of samples. When the data comes from a finite domain, we improve over the baseline by a factor of m in the sample complexity. When the data comes from a Gaussian, Ghazi et al. (Neurips '23) show that single-sampling can be performed under approximate differential privacy; we show it is possible to single- and multi-sample Gaussians with known covariance subject to pure DP. Our solution uses a variant of the Laplace mechanism that is of independent interest. We also give sample complexity lower bounds, one for strong multi-sampling of finite distributions and another for weak multi-sampling of bounded-covariance Gaussians.