  We construct a universally Bayes consistent learning rule that satisfies
differential privacy (DP). We first handle the setting of binary classification
and then extend our rule to the more general setting of density estimation
(with respect to the total variation metric). The existence of a universally
consistent DP learner reveals a stark difference with the distribution-free PAC
model. Indeed, in the latter DP learning is extremely limited: even
one-dimensional linear classifiers are not privately learnable in this
stringent model. Our result thus demonstrates that by allowing the learning
rate to depend on the target distribution, one can circumvent the
above-mentioned impossibility result and in fact, learn \emph{arbitrary}
distributions by a single DP algorithm. As an application, we prove that any VC
class can be privately learned in a semi-supervised setting with a near-optimal
\emph{labeled} sample complexity of $\tilde{O}(d/\varepsilon)$ labeled examples
(and with an unlabeled sample complexity that can depend on the target
distribution).
