# An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 10 May 2025.

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

- [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)
- [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)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [2 Notes on Classes with Vapnik-Chervonenkis Dimension 1](https://mlsanity.com/paper/1507.05307/) (2015)
- [Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity](https://mlsanity.com/paper/2004.07839/) (2020)
- [Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems](https://mlsanity.com/paper/2504.19001/) (2025)

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

- [Learning in an Echo Chamber: Online Learning with Replay Adversary](https://mlsanity.com/paper/2509.25135/) (2025)
- [VALG: An Agentic System for ML Theory Research](https://mlsanity.com/paper/2608.13060/) (2026)

## Abstract (arXiv)

We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension d. Our algorithm achieves the sample complexity of tildeOvarepsilon,δ,α,δ(log^* d), nearly matching the lower bound of Omega(log^* d) proved by Alon et al. [STOC19]. Prior to our work, the best known upper bound is tildeO(VC· d5) for general VC classes, as shown by Ghazi et al. [STOC21].