# Private Learning of Littlestone Classes, Revisited

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 30 Sep 2025.

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

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [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)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [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)
- [Characterizing the Sample Complexity of Private Learners](https://mlsanity.com/paper/1402.2224/) (2014)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [On the Equivalence between Online and Private Learnability beyond Binary Classification](https://mlsanity.com/paper/2006.01980/) (2020)
- [Concurrent Composition of Differential Privacy](https://mlsanity.com/paper/2105.14427/) (2021)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Composition Theorems for Interactive Differential Privacy](https://mlsanity.com/paper/2207.09397/) (2022)
- [Concurrent Composition Theorems for Differential Privacy](https://mlsanity.com/paper/2207.08335/) (2022)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [The Target-Charging Technique for Privacy Accounting across Interactive Computations](https://mlsanity.com/paper/2302.11044/) (2023)

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

- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)

## Abstract (arXiv)

We consider online and PAC learning of Littlestone classes subject to the constraint of approximate differential privacy. Our main result is a private learner to online-learn a Littlestone class with a mistake bound of tildeO(d9.5· log(T)) in the realizable case, where d denotes the Littlestone dimension and T the time horizon. This is a doubly-exponential improvement over the state-of-the-art [GL'21] and comes polynomially close to the lower bound for this task. The advancement is made possible by a couple of ingredients. The first is a clean and refined interpretation of the ``irreducibility'' technique from the state-of-the-art private PAC-learner for Littlestone classes [GGKM'21]. Our new perspective also allows us to improve the PAC-learner of [GGKM'21] and give a sample complexity upper bound of widetildeO(fracd5 log(1/δβ)varepsilon α) where α and β denote the accuracy and confidence of the PAC learner, respectively. This improves over [GGKM'21] by factors of fracdα and attains an optimal dependence on α. Our algorithm uses a private sparse selection algorithm to sample from a pool of strongly input-dependent candidates. However, unlike most previous uses of sparse selection algorithms, where one only cares about the utility of output, our algorithm requires understanding and manipulating the actual distribution from which an output is drawn. In the proof, we use a sparse version of the Exponential Mechanism from [GKM'21] which behaves nicely under our framework and is amenable to a very easy utility proof.