# Private Everlasting Prediction

arXiv: https://arxiv.org/abs/2305.09579 · HTML: https://mlsanity.com/paper/2305.09579/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 16 May 2023.

## Builds on (most cited first, 16 of 16)

- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Privacy-preserving Prediction](https://mlsanity.com/paper/1803.10266/) (2018)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Characterizing the Sample Complexity of Private Learners](https://mlsanity.com/paper/1402.2224/) (2014)
- [Privately Answering Classification Queries in the Agnostic PAC Model](https://mlsanity.com/paper/1907.13553/) (2019)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Learning Privately with Labeled and Unlabeled Examples](https://mlsanity.com/paper/1407.2662/) (2014)
- [PAC learning with stable and private predictions](https://mlsanity.com/paper/1911.10541/) (2019)
- [Robust Mediators in Large Games](https://mlsanity.com/paper/1512.02698/) (2015)
- [Order-Revealing Encryption and the Hardness of Private Learning](https://mlsanity.com/paper/1505.00388/) (2015)

## Built on by (most cited first, 5 of 5)

- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Private Truly-Everlasting Robust-Prediction](https://mlsanity.com/paper/2401.04311/) (2024)
- [Private Prediction via Shrinkage](https://mlsanity.com/paper/2602.05219/) (2026)
- [Barriers to Counterfactual Credit Attribution for Autoregressive Models](https://mlsanity.com/paper/2605.01425/) (2026)

## Abstract (arXiv)

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.