Private Prediction via Shrinkage
Not on the map. Why?
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).
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 14 of its 24 references that are in the map. First posted on arXiv 5 Feb 2026.
Builds on
14 of 24 references.
References · 14
- 2018Private PAC learning implies finite Littlestone dimensioncited by 73
- 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
- 2015Differentially Private Release and Learning of Threshold Functionscited by 58
- 2018Privacy-preserving Predictioncited by 48
- 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
- 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
- 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
- 2019Privately Answering Classification Queries in the Agnostic PAC Modelcited by 18
- 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 16
- 2014Learning Privately with Labeled and Unlabeled Examplescited by 9
- 2020Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexitycited by 8
- 2023Private Everlasting Predictioncited by 5
Built on by
Not cited yet.