Sample Compression Schemes for VC Classes

DOI10.1145/2890490zbMATH Open1426.68239arXiv1503.06960OpenAlexW2231267930MaRDI QIDQ3177793FDOQ3177793

Amir Yehudayoff, Shay Moran

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size $k$ means that given an arbitrary list of labeled examples, one can retain only $k$ of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds. We answer their question and show that every concept class $C$ with VC dimension $d$ has a sample compression scheme of size exponential in $d$. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.

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

Recommendations

• Compression of samplable sources
• Samplets: construction and scattered data compression
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Unlabeled compression schemes exceeding the VC-dimension
• A geometric approach to sample compression
• Recursive teaching dimension, VC-dimension and sample compression
• Sample Compression Schemes for Balls in Graphs
• Teaching and Compressing for Low VC-Dimension
• The Vcodex Platform for Data Compression
• Labeled compression schemes for extremal classes

zbMATH Keywords

PAC learningVC-dimensionsample compression schemes

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)

Cited In (20)

• On the perceptron's compression
• Labeled sample compression schemes for complexes of oriented matroids
• Teaching and Compressing for Low VC-Dimension
• Sample Compression Schemes for Balls in Graphs
• Labeled Compression Schemes for Extremal Classes
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Unlabeled compression schemes exceeding the VC-dimension
• Primal and dual combinatorial dimensions
• Compression schemes for concept classes induced by three types of discrete undirected graphical models
• Inclusion matrices for rainbow subsets
• RAMSEY GROWTH IN SOME NIP STRUCTURES
• The VC-dimension of axis-parallel boxes on the torus
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• A characterization of list learnability
• Two-dimensional partial cubes
• Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids
• Uniformly supported approximate equilibria in families of games
• On uniform definability of types over finite sets for NIP formulas
• Title not available (Why is that?)
• Shattering-extremal set systems from Sperner families

This page was built for publication: Sample Compression Schemes for VC Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177793)