J. Hyam Rubinstein

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. Whether compression schemes of size $O(d)$ must necessarily exist for all clas…