Integral Privacy for Sampling
  Differential privacy is a leading protection setting, focused by design on
individual privacy. Many applications, in medical / pharmaceutical domains or
social networks, rather posit privacy at a group level, a setting we call
integral privacy. We aim for the strongest form of privacy: the group size is
in particular not known in advance. We study a problem with related
applications in domains cited above that have recently met with substantial
recent press: sampling.
  Keeping correct utility levels in such a strong model of statistical
indistinguishability looks difficult to be achieved with the usual differential
privacy toolbox because it would typically scale in the worst case the
sensitivity by the sample size and so the noise variance by up to its square.
We introduce a trick specific to sampling that bypasses the sensitivity
analysis. Privacy enforces an information theoretic barrier on approximation,
and we show how to reach this barrier with guarantees on the approximation of
the target non private density. We do so using a recent approach to non private
density estimation relying on the original boosting theory, learning the
sufficient statistics of an exponential family with classifiers. Approximation
guarantees cover the mode capture problem. In the context of learning, the
sampling problem is particularly important: because integral privacy enjoys the
same closure under post-processing as differential privacy does, any algorithm
using integrally privacy sampled data would result in an output equally
integrally private. We also show that this brings fairness guarantees on
post-processing that would eventually elude classical differential privacy: any
decision process has bounded data-dependent bias when the data is integrally
privately sampled. Experimental results against private kernel density
estimation and private GANs displays the quality of our results.
