The Sample Complexity of Replicable Realizable PAC Learning
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917288147419136 |
|---|---|
| author | Larsen, Kasper Green Mathiasen, Markus Engelund Pabbaraju, Chirag Svendsen, Clement |
| author_facet | Larsen, Kasper Green Mathiasen, Markus Engelund Pabbaraju, Chirag Svendsen, Clement |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19552 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Sample Complexity of Replicable Realizable PAC Learning Larsen, Kasper Green Mathiasen, Markus Engelund Pabbaraju, Chirag Svendsen, Clement Machine Learning Computational Complexity Data Structures and Algorithms 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. |
| title | The Sample Complexity of Replicable Realizable PAC Learning |
| topic | Machine Learning Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.19552 |