Simplicial covering dimension of extremal concept classes
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Labeled compression schemes for extremal classes
It is a long-standing open problem whether there always exists a compression scheme whose size is of the order of the Vapnik-Chervonienkis (VC) dimension $d$. Recently compression schemes of size exponential in $d$ have …
Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
The sample compressibility of concept classes plays an important role in learning theory, as a sufficient condition for PAC learnability, and more recently as an avenue for robust generalisation in adaptive data analysis…
AllLearning TheoryLEMMADual VC Dimension Obstructs Sample Compression by Embeddings
This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddings necessarily require a significant inc…
Learning TheoryUnlabeled sample compression schemes and corner peelings for ample and maximum classes
We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Ou…
BIG-bench Machine LearningThe spectral dimension of simplicial complexes: a renormalization group theory
Simplicial complexes are increasingly used to study complex system structure and dynamics including diffusion, synchronization and epidemic spreading. The spectral dimension of the graph Laplacian is known to determine t…