Limits of Private Learning with Access to Public Data
  We consider learning problems where the training set consists of two types of
examples: private and public. The goal is to design a learning algorithm that
satisfies differential privacy only with respect to the private examples. This
setting interpolates between private learning (where all examples are private)
and classical learning (where all examples are public).
  We study the limits of learning in this setting in terms of private and
public sample complexities. We show that any hypothesis class of VC-dimension
$d$ can be agnostically learned up to an excess error of $\alpha$ using only
(roughly) $d/\alpha$ public examples and $d/\alpha^2$ private labeled examples.
This result holds even when the public examples are unlabeled. This gives a
quadratic improvement over the standard $d/\alpha^2$ upper bound on the public
sample complexity (where private examples can be ignored altogether if the
public examples are labeled). Furthermore, we give a nearly matching lower
bound, which we prove via a generic reduction from this setting to the one of
private learning without public data.
