On Differentially Private Sampling from Gaussian and Product Distributions

Badih Ghazi · Xiao Hu · Ravi Kumar · Pasin Manurangsi

Great Hall & Hall B1+B2 (level 1) #817
[ ]
Tue 12 Dec 8:45 a.m. PST — 10:45 a.m. PST

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.

Chat is not available.