# Private Prediction via Shrinkage

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 24 references that are in the map.
- First posted on arXiv 5 Feb 2026.

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

- [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)
- [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)
- [Learning Privately with Labeled and Unlabeled Examples](https://mlsanity.com/paper/1407.2662/) (2014)
- [Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity](https://mlsanity.com/paper/2004.07839/) (2020)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems](https://mlsanity.com/paper/2504.19001/) (2025)
- [Private Truly-Everlasting Robust-Prediction](https://mlsanity.com/paper/2401.04311/) (2024)

## Abstract (arXiv)

We study differentially private prediction introduced by Dwork and Feldman (COLT 2018): an algorithm receives one labeled sample set S and then answers a stream of unlabeled queries while the output transcript remains (varepsilon,δ)-differentially private with respect to S. Standard composition yields a √T dependence for T queries. We show that this dependence can be reduced to polylogarithmic in T in streaming settings. For an oblivious online adversary and any concept class C, we give a private predictor that answers T queries with |S|= tildeO(VC(C)3.5log3.5T) labeled examples. For an adaptive online adversary and halfspaces over ℝd, we obtain |S|=tildeOleft(d5.5log Tright).