Linear-size sample compression for binary concept classes
Let $X$ be a finite set and let $\varnothing \ne \mathcal C \subseteq \{0,1\}^X$ be a concept class of VC dimension $d \ge 1$. Let $\mathcal S_{\mathcal C}$ be the set of labelled samples $S \subseteq X \times \{0,1\}$ that agree with some $c \in \mathcal C$. A sample compression scheme for $\mathcal C$ is a pair of maps $$\kappa : \mathcal S_{\mathcal C} \to \mathcal S_{\mathcal C} \times \{0,1\}^*, \qquad \rho : \mathcal S_{\mathcal C} \times \{0,1\}^* \to \{0,1\}^X,$$ where $\{0,1\}^*$ is the set of finite bitstrings, such that for every $S \in \mathcal S_{\mathcal C}$, writing $\kappa(S) = (T, b)$, we have $T \subseteq S$ and $\rho(T, b)(x) = y$ for every $(x, y) \in S$. Its size is $\max_S |T| + \max_S |b|$, both maxima over $S \in \mathcal S_{\mathcal C}$. The retained sample $T$ is an unordered set, so any ordering must be encoded in $b$; the reconstruction $\rho(T, b)$ need not belong to $\mathcal C$, and no bound on computation is imposed.
Littlestone and Warmuth introduced sample compression schemes and showed that they yield PAC learners. Floyd and Warmuth constructed schemes of size $d$ for maximum classes, and Moran and Yehudayoff proved that every class of VC dimension $d$ has a scheme of size $2^{O(d)}$.
Problem. Is there a universal constant $K$ such that, for every finite set $X$, every such class $\mathcal C$ admits a sample compression scheme of size at most $Kd$?
Source: Floyd and Warmuth (1995), the sample compression conjecture, after Littlestone and Warmuth (1986); see Warmuth (2003). In this form, with a retained subsample and a bitstring, Bourneuf, Hodor, Micek and Rambaud (2026), §1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- ST
- Keywords
- AIM Open Applied Problems, sample compression schemes, VC dimension
References
@article{floyd1995,
author = {Floyd, Sally and Warmuth, Manfred K.},
title = {Sample compression, learnability, and the {V}apnik--{C}hervonenkis dimension},
journal = {Mach. Learn.},
volume = {21},
number = {3},
year = {1995},
pages = {269--304},
doi = {10.1007/BF00993593},
}
@unpublished{littlestone1986,
author = {Littlestone, Nick and Warmuth, Manfred K.},
title = {Relating data compression and learnability},
note = {Unpublished manuscript},
year = {1986},
}
@incollection{warmuth2003,
author = {Warmuth, Manfred K.},
title = {Compressing to {VC} dimension many points},
booktitle = {Learning Theory and Kernel Machines (COLT/Kernel 2003)},
series = {Lecture Notes in Comput. Sci.},
volume = {2777},
publisher = {Springer},
address = {Berlin},
year = {2003},
pages = {743--744},
doi = {10.1007/978-3-540-45167-9_60},
}
@misc{bourneuf2026,
author = {Bourneuf, Romain and Hodor, J{\k{e}}drzej and Micek, Piotr and Rambaud, Cl{\'e}ment},
title = {Sample compression schemes for balls in structurally sparse graphs},
year = {2026},
eprint = {2604.02949},
archivePrefix = {arXiv},
}
@article{moran2016,
author = {Moran, Shay and Yehudayoff, Amir},
title = {Sample compression schemes for {VC} classes},
journal = {J. ACM},
volume = {63},
number = {3},
year = {2016},
pages = {21:1--21:10},
doi = {10.1145/2890490},
eprint = {1503.06960},
archivePrefix = {arXiv},
}
@misc{aim-linear-sample-compression,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Linear-size sample compression for binary concept classes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/307-linear-sample-compression.md},
note = {Entry 307 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00293, "Linear-size sample compression for binary concept classes", clopen.solutions.