Optimally compressing VC classes

2022/01/11 by Zachary Chase, Chase, Zachary
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Mathematical Analysis and Transform Methods #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2201.04131

Abstract

Resolving a conjecture of Littlestone and Warmuth, we show that any concept class of VC-dimension d has a sample compression scheme of size d.

Related

• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension
• Sample compression schemes for VC classes
• Teaching and compressing for low VC-dimension
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
• Unlabeled Compression Schemes Exceeding the VC-dimension