Simplicial covering dimension of extremal concept 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_ | 1866908654521810944 |
|---|---|
| author | Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan |
| author_facet | Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan |
| contents | Dimension theory is a branch of topology concerned with defining and analyzing dimensions of geometric and topological spaces in purely topological terms. In this work, we adapt the classical notion of topological dimension (Lebesgue covering) to binary concept classes. The topological space naturally associated with a concept class is its space of realizable distributions. The loss function and the class itself induce a simplicial structure on this space, with respect to which we define a simplicial covering dimension.
We prove that for finite concept classes, this simplicial covering dimension exactly characterizes the list replicability number (equivalently, global stability) in PAC learning. This connection allows us to apply tools from classical dimension theory to compute the exact list replicability number of the broad family of extremal concept classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11819 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simplicial covering dimension of extremal concept classes Blondal, Ari Hatami, Hamed Hatami, Pooya Lalov, Chavdar Tretiak, Sivan Machine Learning Algebraic Topology Dimension theory is a branch of topology concerned with defining and analyzing dimensions of geometric and topological spaces in purely topological terms. In this work, we adapt the classical notion of topological dimension (Lebesgue covering) to binary concept classes. The topological space naturally associated with a concept class is its space of realizable distributions. The loss function and the class itself induce a simplicial structure on this space, with respect to which we define a simplicial covering dimension. We prove that for finite concept classes, this simplicial covering dimension exactly characterizes the list replicability number (equivalently, global stability) in PAC learning. This connection allows us to apply tools from classical dimension theory to compute the exact list replicability number of the broad family of extremal concept classes. |
| title | Simplicial covering dimension of extremal concept classes |
| topic | Machine Learning Algebraic Topology |
| url | https://arxiv.org/abs/2511.11819 |