![[2602.19552] The Sample Complexity of Replicable Realizable PAC Learning](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.19552] The Sample Complexity of Replicable Realizable PAC Learning
Summary
This paper explores the sample complexity of replicable realizable PAC learning, establishing a lower bound on sample complexity with novel techniques and providing an upper bound that closely matches the lower bound instance.
Why It Matters
Understanding the sample complexity in PAC learning is crucial for advancing machine learning theory. This research contributes to the foundational knowledge necessary for developing more efficient learning algorithms, especially in contexts where replicability is essential.
Key Takeaways
- Establishes a lower bound for sample complexity in PAC learning related to the size of the hypothesis class.
- Introduces novel techniques involving Cayley graphs and spectral properties for analysis.
- Provides an upper bound that closely matches the established lower bound, indicating the robustness of the findings.
- Highlights the importance of replicability in machine learning models.
- Encourages further exploration of different instances for stronger lower bounds.
Computer Science > Machine Learning arXiv:2602.19552 (cs) [Submitted on 23 Feb 2026] Title:The Sample Complexity of Replicable Realizable PAC Learning Authors:Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen View a PDF of the paper titled The Sample Complexity of Replicable Realizable PAC Learning, by Kasper Green Larsen and 3 other authors View PDF HTML (experimental) Abstract:In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem. Subjects: Machine Learning (cs.LG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2602.19552 [cs.LG] (or arXiv:2602.19552v1 [cs.LG] for this version) https://doi.org/10.48550/arXiv.2602.19552 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Kasper Green Larsen [view email] [v1] Mon, 23 Feb 2026 06:52:11 UTC (44 KB) Full-t...
