On Differentially Private Sampling from Gaussian and Product Distributions

Given a dataset of n i.i.d. samples from an unknown distribution P, we consider the problem of generating a sample from a distribution that is close to P in total variation distance, under the constraint of differential privacy (DP). We study the problem when P is a multi-dimensional Gaussian distribution, under different assumptions on the information available to the DP mechanism: known covariance, unknown bounded covariance, and unknown unbounded covariance. We present new DP 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.