Learning Privately with Labeled and Unlabeled Examples
  A private learner is an algorithm that given a sample of labeled individual
examples outputs a generalizing hypothesis while preserving the privacy of each
individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a generic
construction of private learners, in which the sample complexity is (generally)
higher than what is needed for non-private learners. This gap in the sample
complexity was then further studied in several followup papers, showing that
(at least in some cases) this gap is unavoidable. Moreover, those papers
considered ways to overcome the gap, by relaxing either the privacy or the
learning guarantees of the learner.
  We suggest an alternative approach, inspired by the (non-private) models of
semi-supervised learning and active-learning, where the focus is on the sample
complexity of labeled examples whereas unlabeled examples are of a
significantly lower cost. We consider private semi-supervised learners that
operate on a random sample, where only a (hopefully small) portion of this
sample is labeled. The learners have no control over which of the sample
elements are labeled. Our main result is that the labeled sample complexity of
private learners is characterized by the VC dimension.
  We present two generic constructions of private semi-supervised learners. The
first construction is of learners where the labeled sample complexity is
proportional to the VC dimension of the concept class, however, the unlabeled
sample complexity of the algorithm is as big as the representation length of
domain elements. Our second construction presents a new technique for
decreasing the labeled sample complexity of a given private learner, while
roughly maintaining its unlabeled sample complexity. In addition, we show that
in some settings the labeled sample complexity does not depend on the privacy
parameters of the learner.
