Private Everlasting Prediction
Moni Naor Kobbi Nissim Uri Stemmer Chao Yan
A private learner is trained on a sample of labeled points and generates a
hypothesis that can be used for predicting the labels of newly sampled points
while protecting the privacy of the training set [Kasiviswannathan et al., FOCS
2008]. Research uncovered that private learners may need to exhibit
significantly higher sample complexity than non-private learners as is the case
with, e.g., learning of one-dimensional threshold functions [Bun et al., FOCS
2015, Alon et al., STOC 2019].
  We explore prediction as an alternative to learning. Instead of putting
forward a hypothesis, a predictor answers a stream of classification queries.
Earlier work has considered a private prediction model with just a single
classification query [Dwork and Feldman, COLT 2018]. We observe that when
answering a stream of queries, a predictor must modify the hypothesis it uses
over time, and, furthermore, that it must use the queries for this
modification, hence introducing potential privacy risks with respect to the
queries themselves.
  We introduce private everlasting prediction taking into account the privacy
of both the training set and the (adaptively chosen) queries made to the
predictor. We then present a generic construction of private everlasting
predictors in the PAC model. The sample complexity of the initial training
sample in our construction is quadratic (up to polylog factors) in the VC
dimension of the concept class. Our construction allows prediction for all
concept classes with finite VC dimension, and in particular threshold functions
with constant size initial training sample, even when considered over infinite
domains, whereas it is known that the sample complexity of privately learning
threshold functions must grow as a function of the domain size and hence is
impossible for infinite domains.