Higher-arity PAC learning, VC dimension and packing lemma
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908593362567168 |
|---|---|
| author | Chernikov, Artem Towsner, Henry |
| author_facet | Chernikov, Artem Towsner, Henry |
| contents | The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that it characterizes higher arity PAC learning (PAC$_n$ learning) in $n$-fold product spaces with respect to product measures introduced by Kobayashi, Kuriyama and Takeuchi'15. We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02420 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Higher-arity PAC learning, VC dimension and packing lemma Chernikov, Artem Towsner, Henry Machine Learning Discrete Mathematics Combinatorics Logic Statistics Theory 68Q32, 05C65, 05C35, 03C45 The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that it characterizes higher arity PAC learning (PAC$_n$ learning) in $n$-fold product spaces with respect to product measures introduced by Kobayashi, Kuriyama and Takeuchi'15. We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726. |
| title | Higher-arity PAC learning, VC dimension and packing lemma |
| topic | Machine Learning Discrete Mathematics Combinatorics Logic Statistics Theory 68Q32, 05C65, 05C35, 03C45 |
| url | https://arxiv.org/abs/2510.02420 |