Privacy-preserving data analysis is emerging as a challenging problem with
far-reaching impact. In particular, synthetic data are a promising concept
toward solving the aporetic conflict between data privacy and data sharing.
Yet, it is known that accurately generating private, synthetic data of certain
kinds is NP-hard. We develop a statistical framework for differentially private
synthetic data, which enables us to circumvent the computational hardness of
the problem. We consider the true data as a random sample drawn from a
population Omega according to some unknown density. We then replace Omega by a
much smaller random subset Omega^*, which we sample according to some known
density. We generate synthetic data on the reduced space Omega^* by fitting the
specified linear statistics obtained from the true data. To ensure privacy we
use the common Laplacian mechanism. Employing the concept of Renyi condition
number, which measures how well the sampling distribution is correlated with
the population distribution, we derive explicit bounds on the privacy and
accuracy provided by the proposed method.

By admin