Epsilon-saturation for stable graphs and Littlestone classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918132706181120 |
|---|---|
| author | Malliaris, Maryanthe del Campo, Olga Medrano Martín Moran, Shay |
| author_facet | Malliaris, Maryanthe del Campo, Olga Medrano Martín Moran, Shay |
| contents | Any Littlestone class, or stable graph, has finite sets which function as ``virtual elements'': these can be seen from the learning side as representing hypotheses which are expressible as weighted majority opinions of hypotheses in the class, and from the model-theoretic side as an approximate finitary version of realizing types. We introduce and study the epsilon-saturation of a Littlestone class, or stable graph, which is essentially the closure of the class under inductively adding all such virtual elements. We characterize this closure and prove that under reasonable choices of parameters, it remains Littlestone (or stable), though not always of the same Littlestone dimension. This highlights some surprising phenomena having to do with regimes of epsilon and the relation between Littlestone/stability and VC dimension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21807 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Epsilon-saturation for stable graphs and Littlestone classes Malliaris, Maryanthe del Campo, Olga Medrano Martín Moran, Shay Logic Discrete Mathematics Logic in Computer Science Combinatorics Any Littlestone class, or stable graph, has finite sets which function as ``virtual elements'': these can be seen from the learning side as representing hypotheses which are expressible as weighted majority opinions of hypotheses in the class, and from the model-theoretic side as an approximate finitary version of realizing types. We introduce and study the epsilon-saturation of a Littlestone class, or stable graph, which is essentially the closure of the class under inductively adding all such virtual elements. We characterize this closure and prove that under reasonable choices of parameters, it remains Littlestone (or stable), though not always of the same Littlestone dimension. This highlights some surprising phenomena having to do with regimes of epsilon and the relation between Littlestone/stability and VC dimension. |
| title | Epsilon-saturation for stable graphs and Littlestone classes |
| topic | Logic Discrete Mathematics Logic in Computer Science Combinatorics |
| url | https://arxiv.org/abs/2508.21807 |