# PAC learning with stable and private predictions

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2019.

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

- [Differentially Private Decoding in Large Language Models](https://mlsanity.com/paper/2205.13621/) (2022)
- [Integration of Large Language Models and Federated Learning](https://mlsanity.com/paper/2307.08925/) (2023)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [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)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Private Truly-Everlasting Robust-Prediction](https://mlsanity.com/paper/2401.04311/) (2024)
- [Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness](https://mlsanity.com/paper/2506.03075/) (2025)
- [Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2510.01291/) (2025)

## Abstract (arXiv)

We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. Unfortunately, this approach leads to a significant overhead in terms of sample complexity. Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. Specifically, we demonstrate that for any class C of VC dimension d there exists a γ-uniformly stable algorithm for learning C with excess error α using tilde O(d/(αγ) + d/α2) samples. We also show that this bound is nearly tight. For ε-differentially private prediction we give two new algorithms: one using tilde O(d/(α2ε)) samples and another one using tilde O(d2/(αε) + d/α2) samples. The best previously known bounds for these problems are O(d/(α2γ)) and O(d/(α3ε)), respectively.