# A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 24 Dec 2022.

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

- [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)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Optimal Collusion-Free Teaching](https://mlsanity.com/paper/1903.04012/) (2019)
- [Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes](https://mlsanity.com/paper/1702.05677/) (2017)

## Abstract (arXiv)

This paper presents a construction of a proper and stable labelled sample compression scheme of size O(VCD2) for any finite concept class, where VCD denotes the Vapnik-Chervonenkis Dimension. The construction is based on a well-known model of machine teaching, referred to as recursive teaching dimension. This substantially improves on the currently best known bound on the size of sample compression schemes (due to Moran and Yehudayoff), which is exponential in VCD. The long-standing open question whether the smallest size of a sample compression scheme is in O(VCD) remains unresolved, but our results show that research on machine teaching is a promising avenue for the study of this open problem. As further evidence of the strong connections between machine teaching and sample compression, we prove that the model of no-clash teaching, introduced by Kirkpatrick et al., can be used to define a non-trivial lower bound on the size of stable sample compression schemes.