  Ensuring differential privacy of models learned from sensitive user data is
an important goal that has been studied extensively in recent years. It is now
known that for some basic learning problems, especially those involving
high-dimensional data, producing an accurate private model requires much more
data than learning without privacy. At the same time, in many applications it
is not necessary to expose the model itself. Instead users may be allowed to
query the prediction model on their inputs only through an appropriate
interface. Here we formulate the problem of ensuring privacy of individual
predictions and investigate the overheads required to achieve it in several
standard models of classification and regression.
  We first describe a simple baseline approach based on training several models
on disjoint subsets of data and using standard private aggregation techniques
to predict. We show that this approach has nearly optimal sample complexity for
(realizable) PAC learning of any class of Boolean functions. At the same time,
without strong assumptions on the data distribution, the aggregation step
introduces a substantial overhead. We demonstrate that this overhead can be
avoided for the well-studied class of thresholds on a line and for a number of
standard settings of convex regression. The analysis of our algorithm for
learning thresholds relies crucially on strong generalization guarantees that
we establish for all differentially private prediction algorithms.
