Unlabeled sample compression schemes and corner peelings for ample and maximum classes

DOI10.1016/j.jcss.2022.01.003zbMath1483.68281arXiv1812.02099OpenAlexW2902050609WikidataQ114162790 ScholiaQ114162790MaRDI QIDQ2121466

Manfred K. Warmuth, Victor Chepoi, Shay Moran, Jérémie Chalopin

Publication date: 4 April 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.02099

zbMATH Keywords

VC-dimensionunique sink orientationsample compressionample classcorner peelingextremal classmaximum classsandwich lemmaSauer-Shelah-Perles lemma

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Shellability for polytopes and polyhedra (52B22)

Related Items (3)

What convex geometries tell about shattering-extremal systems ⋮ Sample Compression Schemes for Balls in Graphs ⋮ First-order logic axiomatization of metric graph theory

Cites Work

• Shattering, graph orientations, and connectivity
• Shattering-extremal set systems of VC dimension at most 2
• The theory of convex geometries
• \(\epsilon\)-nets and simplex range queries
• Petri nets, event structures and domains. I
• Lopsided sets and orthant-intersection by convex sets
• The uniquely solvable bipartite matching problem
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• Shattering news
• Morse theory for cell complexes
• COMs: complexes of oriented matroids
• Defect Sauer results
• Collapsibility of CAT(0) spaces
• Unlabeled compression schemes exceeding the VC-dimension
• Some new maximum VC classes
• Independent systems of representatives in weighted graphs
• Combinatorics of lopsided sets
• The number of unique-sink orientations of the hypercube
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Labeled Compression Schemes for Extremal Classes
• Generalizing Labeled and Unlabeled Sample Compression to Multi-label Concept Classes
• Sample Compression Schemes for VC Classes
• Lectures on Polytopes
• Mathematics and Computation
• A Geometric Approach to Sample Compression
• Understanding Machine Learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Recognition of collapsible complexes is NP-complete
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Unlabeled sample compression schemes and corner peelings for ample and maximum classes