On Differentially Private Sampling from Gaussian and Product Distributions
Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
Abstract
We study the problem, where given a dataset of $n$ i.i.d. samples from an unknown distribution $P$, we seek to generate a sample from a distribution that is close to $P$ in total variation distance, under the constraint of differential privacy. We study the settings where $P$ is a multi-dimensional Gaussian distribution with different assumptions: known covariance, unknown bounded covariance, and unknown unbounded covariance. We present new differentially private sampling algorithms, and show that they achieve near-optimal sample complexity in the first two settings. Moreover, when $P$ is a product distribution on the binary hypercube, we obtain a pure-DP algorithm whereas only an approximate-DP algorithm (with slightly worse sample complexity) was previously known.
BibTeX
@inproceedings{
ghazi2023on,
title={On Differentially Private Sampling from Gaussian and Product Distributions},
author={Badih Ghazi and Xiao Hu and Ravi Kumar and Pasin Manurangsi},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=FviF8vuz5B}
}