# Private PAC Learning May be Harder than Online Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 16 Feb 2024.

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

- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [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)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014)
- [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)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Indistinguishability Obfuscation from Well-Founded Assumptions](https://mlsanity.com/paper/2008.09317/) (2020)
- [Private Learning Implies Online Learning: An Efficient Reduction](https://mlsanity.com/paper/1905.11311/) (2019)
- [A Computational Separation between Private Learning and Online Learning](https://mlsanity.com/paper/2007.05665/) (2020)
- [Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique](https://mlsanity.com/paper/2211.01443/) (2022)
- [Order-Revealing Encryption and the Hardness of Private Learning](https://mlsanity.com/paper/1505.00388/) (2015)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling](https://mlsanity.com/paper/2105.00743/) (2021)

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

- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Expressivity of Contradiction Graphs](https://mlsanity.com/paper/2605.20434/) (2026)

## Abstract (arXiv)

We continue the study of the computational complexity of differentially private PAC learning and how it is situated within the foundations of machine learning. A recent line of work uncovered a qualitative equivalence between the private PAC model and Littlestone's mistake-bounded model of online learning, in particular, showing that any concept class of Littlestone dimension d can be privately PAC learned using poly(d) samples. This raises the natural question of whether there might be a generic conversion from online learners to private PAC learners that also preserves computational efficiency. We give a negative answer to this question under reasonable cryptographic assumptions (roughly, those from which it is possible to build indistinguishability obfuscation for all circuits). We exhibit a concept class that admits an online learner running in polynomial time with a polynomial mistake bound, but for which there is no computationally-efficient differentially private PAC learner. Our construction and analysis strengthens and generalizes that of Bun and Zhandry (TCC 2016-A), who established such a separation between private and non-private PAC learner.