# Privacy-preserving Prediction

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2018.

## Built on by (most cited first, 30 of 48)

- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [On Provable Copyright Protection for Generative Models](https://mlsanity.com/paper/2302.10870/) (2023)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Differentially Private Decoding in Large Language Models](https://mlsanity.com/paper/2205.13621/) (2022)
- [Submix: Practical Private Prediction for Large-Scale Language Models](https://mlsanity.com/paper/2201.00971/) (2022)
- [One Parameter Defense -- Defending against Data Inference Attacks via Differential Privacy](https://mlsanity.com/paper/2203.06580/) (2022)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Can Copyright be Reduced to Privacy?](https://mlsanity.com/paper/2305.14822/) (2023)
- [Private prediction for large-scale synthetic text generation](https://mlsanity.com/paper/2407.12108/) (2024)
- [Differentially Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2403.15638/) (2024)
- [Gaussian Membership Inference Privacy](https://mlsanity.com/paper/2306.07273/) (2023)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Machine Unlearning: A Survey](https://mlsanity.com/paper/2306.03558/) (2023)
- [Purifier: Defending Data Inference Attacks via Transforming Confidence Scores](https://mlsanity.com/paper/2212.00612/) (2022)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [Information Flow Control in Machine Learning through Modular Model Architecture](https://mlsanity.com/paper/2306.03235/) (2023)
- [Not All Similarities Are Created Equal: Leveraging Data-Driven Biases to Inform GenAI Copyright Disputes](https://mlsanity.com/paper/2403.17691/) (2024)
- [SoK: Modeling Explainability in Security Analytics for Interpretability, Trustworthiness, and Usability](https://mlsanity.com/paper/2210.17376/) (2022)
- [Deep Generative Models, Synthetic Tabular Data, and Differential Privacy: An Overview and Synthesis](https://mlsanity.com/paper/2307.15424/) (2023)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [Differential privacy for medical deep learning: methods, tradeoffs, and deployment implications](https://mlsanity.com/paper/2506.00660/) (2025)
- [DP-Fusion: Token-Level Differentially Private Inference for Large Language Models](https://mlsanity.com/paper/2507.04531/) (2025)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- ["Private Prediction Strikes Back!'' Private Kernelized Nearest Neighbors with Individual Renyi Filter](https://mlsanity.com/paper/2306.07381/) (2023)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [Clustering and Median Aggregation Improve Differentially Private Inference](https://mlsanity.com/paper/2506.04566/) (2025)
- [Adaptively Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2410.02016/) (2024)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)

## Abstract (arXiv)

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.