# Dual VC Dimension Obstructs Sample Compression by Embeddings

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 48 references that are in the map.
- First posted on arXiv 27 May 2024.

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

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [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)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Sample compression schemes for balls in graphs](https://mlsanity.com/paper/2206.13254/) (2022)
- [Labeled sample compression schemes for complexes of oriented matroids](https://mlsanity.com/paper/2110.15168/) (2021)
- [Bounding Embeddings of VC Classes into Maximum Classes](https://mlsanity.com/paper/1401.7388/) (2014)
- [Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes](https://mlsanity.com/paper/2210.05455/) (2022)

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

- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)

## Abstract (arXiv)

This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddings necessarily require a significant increase in dimension. In particular, we prove that for every d there is a class with VC dimension d that cannot be embedded in any extremal class of VC dimension smaller than exponential in d. In addition to its independent interest, this result has an important implication in learning theory, as it reveals a fundamental limitation of one of the most extensively studied approaches to tackling the long-standing sample compression conjecture. Concretely, the approach proposed by Floyd and Warmuth entails embedding any given VC class into an extremal class of a comparable dimension, and then applying an optimal sample compression scheme for extremal classes. However, our results imply that this strategy would in some cases result in a sample compression scheme at least exponentially larger than what is predicted by the sample compression conjecture. The above implications follow from a general result we prove: any extremal class with VC dimension d has dual VC dimension at most 2d+1. This bound is exponentially smaller than the classical bound 2d+1-1 of Assouad, which applies to general concept classes (and is known to be unimprovable for some classes). We in fact prove a stronger result, establishing that 2d+1 upper bounds the dual Radon number of extremal classes. This theorem represents an abstraction of the classical Radon theorem for convex sets, extending its applicability to a wider combinatorial framework, without relying on the specifics of Euclidean convexity. The proof utilizes the topological method and is primarily based on variants of the Topological Radon Theorem.