# Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes

arXiv: https://arxiv.org/abs/2210.05455 · HTML: https://mlsanity.com/paper/2210.05455/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 11 Oct 2022.

## Builds on (most cited first, 6 of 6)

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Adaptive Learning with Robust Generalization Guarantees](https://mlsanity.com/paper/1602.07726/) (2016)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Unlabeled Compression Schemes Exceeding the VC-dimension](https://mlsanity.com/paper/1811.12471/) (2018)
- [Bounding Embeddings of VC Classes into Maximum Classes](https://mlsanity.com/paper/1401.7388/) (2014)

## Built on by (most cited first, 5 of 5)

- [Dual VC Dimension Obstructs Sample Compression by Embeddings](https://mlsanity.com/paper/2405.17120/) (2024)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [Learning in an Echo Chamber: Online Learning with Replay Adversary](https://mlsanity.com/paper/2509.25135/) (2025)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)

## Abstract (arXiv)

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 classes of VC dimension d is unknown, but conjectured to be true by Warmuth. Recently Chalopin, Chepoi, Moran, and Warmuth (2018) gave a beautiful unlabelled sample compression scheme of size VC dimension for all maximum classes: classes that meet the Sauer-Shelah-Perles Lemma with equality. They also offered a counterexample to compression schemes based on a promising approach known as corner peeling. In this paper we simplify and extend their proof technique to deal with so-called extremal classes of VC dimension d which contain maximum classes of VC dimension d-1. A criterion is given which would imply that all extremal classes admit unlabelled compression schemes of size d. We also prove that all intersection-closed classes with VC dimension d admit unlabelled compression schemes of size at most 11d.