# Private Prediction via PAC Privacy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 63 references that are in the map.
- First posted on arXiv 20 Jan 2026.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Features](https://mlsanity.com/paper/1905.04899/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Privacy-preserving Prediction](https://mlsanity.com/paper/1803.10266/) (2018)
- [Submix: Practical Private Prediction for Large-Scale Language Models](https://mlsanity.com/paper/2201.00971/) (2022)
- [Model-as-a-Service (MaaS): A Survey](https://mlsanity.com/paper/2311.05804/) (2023)
- [The Trade-Offs of Private Prediction](https://mlsanity.com/paper/2007.05089/) (2020)
- [PAC Privacy: Automatic Privacy Measurement and Control of Data Processing](https://mlsanity.com/paper/2210.03458/) (2022)
- [Differentially Private Image Classification by Learning Priors from Random Processes](https://mlsanity.com/paper/2306.06076/) (2023)
- [OSLO: One-Shot Label-Only Membership Inference Attacks](https://mlsanity.com/paper/2405.16978/) (2024)
- [Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic Survey](https://mlsanity.com/paper/2309.16398/) (2023)
- [Why Does Differential Privacy with Large Epsilon Defend Against Practical Membership Inference Attacks?](https://mlsanity.com/paper/2402.09540/) (2024)
- [Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD](https://mlsanity.com/paper/2601.10237/) (2026)
- [Residual-PAC Privacy: Automatic Privacy Control Beyond the Gaussian Barrier](https://mlsanity.com/paper/2506.06530/) (2025)

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

- [PACZero: PAC-Private Fine-Tuning of Language Models via Sign Quantization](https://mlsanity.com/paper/2605.06505/) (2026)

## Abstract (arXiv)

Machine learning models are increasingly served behind APIs. This renders private prediction, i.e., privatizing a model's outputs rather than its parameters, a natural privacy target: model outputs are lower-dimensional and far more stable to training-data changes than weights. While differential privacy (DP) cannot effectively exploit this as it calibrates noise to worst-case sensitivity that is intractable to bound for non-convex models, we argue that PAC privacy is a natural fit for private prediction. It is instance-based, and calibrates noise to a black-box function's empirical stability to control mutual-information (MI) leakage. The missing ingredient is efficient, adaptive composition. Serving predictions means answering a long stream of adaptively chosen queries from untrusted users; existing composition either fails under adaptivity, grows quadratically, or reverts to input-independent, DP-like noise. We close this gap with a new adversarial composition result via adaptive noise calibration and prove that MI accumulates only linearly under adaptive and adversarial querying. Experiments across modalities show that prediction stability enables high utility even at a tiny per-query budget: on CIFAR-10, we achieve 87.79% accuracy with a per-query MI budget of 2-32. This enables serving one million queries while provably bounding membership-inference success to 51.08% -- the same guarantee as (0.04, 10-5)-DP. Further, in the presence of auxiliary public data, the large volume of PAC-private predictions enables us to distill a publishable model that can be queried without limit. Concretely, 210,000 private labels on an ImageNet subset distill into a student reaching 91.86% accuracy on CIFAR-10 with membership inference success bounded by 50.49%, comparable to (0.02, 10-5)-DP.