mlsanityData to 7 Oct 2026

Private PAC learning implies finite Littlestone dimension

arXiv 1806.00949 ↗First posted 4 Jun 2018cs.LG cs.AI cs.CRcited by 73

Not on the map. Why?

Abstract (arXiv)

We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension~d requires Omegabigl(log^*(d)bigr) examples. As a corollary it follows that the class of thresholds over mathbbN can not be learned in a private manner; this resolves open question due to [Bun et al., 2015, Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.

Key facts. Cited by 73 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jun 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 12; 2023: 14; 2024: 13; 2025: 11; 2026: 7.

73 papers.

Sort:

  1. 2021Deep Learning with Label Differential Privacycited by 113
  2. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  3. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  4. 2022Private Synthetic Data for Multitask Learning and Marginal Queriescited by 35
  5. 2021Realizable Learning is All You Needcited by 25
  6. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  7. 2021Understanding the Eluder Dimensioncited by 19
  8. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  9. 2022How unfair is private learning ?cited by 18
  10. 2021Majorizing Measures, Sequential Complexities, and Online Learningcited by 17
  11. 2023Statistical Indistinguishability of Learning Algorithmscited by 17
  12. 2024Efficient and Near-Optimal Noise Generation for Streaming Differential Privacycited by 17
38 more
  1. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  2. 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 16
  3. 2023List and Certificate Complexities in Replicable Learningcited by 13
  4. 2023The Bayesian Stability Zoocited by 13
  5. 2023A Trichotomy for Transductive Online Learningcited by 13
  6. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
  7. 2023Online Learning and Solving Infinite Games with an ERM Oraclecited by 11
  8. 2021Private learning implies quantum stabilitycited by 10
  9. 2021Littlestone Classes are Privately Online Learnablecited by 10
  10. 2021User-Level Private Learning via Correlated Samplingcited by 9
  11. 2023On Differential Privacy and Adaptive Data Analysis with Bounded Spacecited by 9
  12. 2025Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Backcited by 9
  13. 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
  14. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  15. 2024Multiclass Transductive Online Learningcited by 8
  16. 2022Differentially Private Learning with Margin Guaranteescited by 7
  17. 2022Finite Littlestone Dimension Implies Finite Information Complexitycited by 7
  18. 2022Instance-Optimal Differentially Private Estimationcited by 7
  19. 2024On the Computational Landscape of Replicable Learningcited by 7
  20. 2024Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theoremcited by 6
  21. 2023A Unified Characterization of Private Learnability via Graph Theorycited by 5
  22. 2023Private Everlasting Predictioncited by 5
  23. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  24. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 5
  25. 2024On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspectivecited by 5
  26. 2024Online Classification with Predictionscited by 5
  27. 2024The Limits of Differential Privacy in Online Learningcited by 5
  28. 2021Multiclass versus Binary Differentially Private PAC Learningcited by 4
  29. 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
  30. 2022Do you pay for Privacy in Online learning?cited by 4
  31. 2022The unstable formula theorem revisited via algorithmscited by 4
  32. 2024Private PAC Learning May be Harder than Online Learningcited by 4
  33. 2025Stability and List-Replicability for Agnostic Learnerscited by 4
  34. 2025Spherical dimensioncited by 4
  35. 2021Differentially Private Nonparametric Regression Under a Growth Conditioncited by 3
  36. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  37. 2024Private Geometric Mediancited by 3
  38. 2024Credit Attribution and Stable Compressioncited by 3

50 most cited of 73 All 73 (JSON)