mlsanityData to 14 Oct 2026

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

arXiv 2505.06581 ↗First posted 10 May 2025cs.LG cs.CRcited by 2

Not on the map. Why?

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].

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

12 of 24 references.

References · 12

  1. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  2. 2020An Equivalence Between Private Classification and Online Predictioncited by 64
  3. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 63
  4. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  5. 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
  6. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
  7. 2020Sample-efficient proper PAC learning with approximate differential privacycited by 29
  8. 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 18
  9. 2019Private Center Points and Learning of Halfspacescited by 14
  10. 20152 Notes on Classes with Vapnik-Chervonenkis Dimension 1cited by 12
  11. 2020Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexitycited by 9
  12. 2025Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problemscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Learning in an Echo Chamber: Online Learning with Replay Adversarycited by 3
  2. 2026VALG: An Agentic System for ML Theory Researchcited by 2