Private Everlasting Prediction

A private learner is trained on a sample of labeled points and generates1 a hypothesis that can be used for predicting the labels of newly sampled2 points while protecting the privacy of the training set [Kasiviswannathan3 et al., FOCS 2008]. Research uncovered that private learners may need to4 exhibit significantly higher sample complexity than non-private learners5 as is the case with, e.g., learning of one-dimensional threshold functions6 [Bun et al., FOCS 2015, Alon et al., STOC 2019].7 We explore prediction as an alternative to learning. Instead of putting8 forward a hypothesis, a predictor answers a stream of classification queries.9 Earlier work has considered a private prediction model with just a single10 classification query [Dwork and Feldman, COLT 2018]. We observe that11 when answering a stream of queries, a predictor must modify the hypothesis12 it uses over time, and, furthermore, that it must use the queries for this13 modification, hence introducing potential privacy risks with respect to the14 queries themselves.15 We introduce private everlasting prediction taking into account the privacy16 of both the training set and the (adaptively chosen) queries made to the17 predictor. We then present a generic construction of private everlasting18 predictors in the PAC model. The sample complexity of the initial training19 sample in our construction is quadratic (up to polylog factors) in the VC20 dimension of the concept class. Our construction allows prediction for21 all concept classes with finite VC dimension, and in particular threshold22 functions with constant size initial training sample, even when considered23 over infinite domains, whereas it is known that the sample complexity24 of privately learning threshold functions must grow as a function of the25 domain size and hence is impossible for infinite domains.26