mlsanityData to 7 Oct 2026

The Optimal Sample Complexity of PAC Learning

arXiv 1507.00473 ↗First posted 2 Jul 2015cs.LG stat.MLcited by 72

Not on the map. Why?

Abstract (arXiv)

This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case. The bound matches known lower bounds up to numerical constant factors. This solves a long-standing open problem on the sample complexity of PAC learning. The technique and analysis build on a recent breakthrough by Hans Simon.

Key facts. Cited by 72 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 10; 2023: 7; 2024: 11; 2025: 10; 2026: 27.

72 papers.

Sort:

By area:

  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  2. 2022Bagging is an Optimal PAC Learnercited by 34
  3. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  4. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  5. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  6. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  7. 2024Majority-of-Three: The Simplest Optimal Learner?cited by 17
  8. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  9. 2021Robust learning under clean-label attackcited by 15
  10. 2022Optimal Weak to Strong Learningcited by 14
  11. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  12. 2023The sample complexity of multi-distribution learningcited by 12
38 more
  1. 2022The One-Inclusion Graph Algorithm is not Always Optimalcited by 11
  2. 2024Revisiting Agnostic PAC Learningcited by 11
  3. 2022Adversarially Robust Learning with Tolerancecited by 9
  4. 2021Bounded Memory Active Learning through Enriched Queriescited by 8
  5. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  6. 2026The Optimal Sample Complexity of Multiclass and List Learningcited by 8
  7. 2022Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Bicliquecited by 7
  8. 2023AdaBoost is not an Optimal Weak to Strong Learnercited by 6
  9. 2025Is Limited Participant Diversity Impeding EEG-based Machine Learning?cited by 6
  10. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  11. 2024Inference, interference and invariance: How the Quantum Fourier Transform can help to learn from datacited by 5
  12. 2025On Agnostic PAC Learning in the Small Error Regimecited by 5
  13. 2025Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigationcited by 5
  14. 2023Optimal lower bounds for Quantum Learning via Information Theorycited by 4
  15. 2024Is Transductive Learning Equivalent to PAC Learning?cited by 4
  16. 2025Improved Margin Generalization Bounds for Voting Classifierscited by 4
  17. 2026Learning with Monotone Adversarial Corruptionscited by 4
  18. 2026An Optimal Sauer Lemma Over k-ary Alphabetscited by 4
  19. 2026Majority-of-Three is Optimalcited by 4
  20. 2023Quantum Learning Theory Beyond Batch Binary Classificationcited by 3
  21. 2024Distribution-Free Rates in Neyman-Pearson Classificationcited by 3
  22. 2024The Many Faces of Optimal Weak-to-Strong Learningcited by 3
  23. 2024Understanding Aggregations of Proper Learners in Multiclass Classificationcited by 3
  24. 2024Universal Rates of Empirical Risk Minimizationcited by 3
  25. 2026Optimal Rates for Learning with Monotone Adversariescited by 3
  26. 2022Is Stochastic Gradient Descent Near Optimal?cited by 2
  27. 2024Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Expertscited by 2
  28. 2025Proper Learnability and the Role of Unlabeled Datacited by 2
  29. 2026An Optimal Agnostic PAC Algorithmcited by 2
  30. 2021Adversarial Robustness: What fools you makes you strongercited by 1
  31. 2022A Survey of Learning on Small Data: Generalization, Optimization, and Challengecited by 1
  32. 2025Universal rates of ERM for agnostic learningcited by 1
  33. 2025Assessing Trustworthiness of AI Training Dataset using Subjective Logic -- A Use Case on Biascited by 1
  34. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1
  35. 2026The Sample Complexity of Replicable Realizable PAC Learningcited by 1
  36. 2022Mixture of Online and Offline Experts for Non-stationary Time Seriescited by 0
  37. 2023Learning Spatial Distribution of Long-Term Trackers Scorescited by 0
  38. 2024Proper vs Improper Quantum PAC learningcited by 0

50 most cited of 72 All 72 (JSON)