Simplicial covering dimension of extremal concept classes
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 17 of its 32 references that are in the map. First posted on arXiv 14 Nov 2025.
Builds on
17 of 32 references.
References · 17
- 2020An Equivalence Between Private Classification and Online Predictioncited by 64
- 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
- 2022Replicable Banditscited by 22
- 2023Replicable Reinforcement Learningcited by 21
- 2023Replicability in Reinforcement Learningcited by 21
- 2023Replicable Clusteringcited by 19
- 2018Unlabeled sample compression schemes and corner peelings for ample and maximum classescited by 16
- 2023Local Borsuk-Ulam, Stability, and Replicabilitycited by 14
- 2023List and Certificate Complexities in Replicable Learningcited by 13
- 2023The Bayesian Stability Zoocited by 13
- 2024Replicable Learning of Large-Margin Halfspacescited by 12
- 2015Labeled compression schemes for extremal classescited by 11
5 more
- 2024Dual VC Dimension Obstructs Sample Compression by Embeddingscited by 5
- 2022The unstable formula theorem revisited via algorithmscited by 4
- 2025Stability and List-Replicability for Agnostic Learnerscited by 4
- 2025Spherical dimensioncited by 4
- 2025Borsuk-Ulam and Replicable Learning of Large-Margin Halfspacescited by 4
Built on by
Citing papers per year: 2026: 2.
2 papers.