TOPICS
Search

Sample Compression Scheme


A sample compression scheme summarizes a finite labeled sample by retaining a bounded number of its examples, possibly with a bounded amount of auxiliary information, so that a fixed reconstruction rule produces a hypothesis agreeing with every label in the original sample (Floyd and Warmuth 1995). For a binary concept class C subset= {0,1}^X, the realizable version applies to every finite sample labeled by some member of C. A labeled scheme of size (k,b) retains an unordered subset of at most k labeled examples and at most b auxiliary bits. Its reconstruction need not be a member of C.

Cai et al. (2026, Theorem 1.1) gave such a scheme for every binary concept class of finite Vapnik-Chervonenkis dimension d>=1, with

 k=O(d^2ln^2(2d)),

and b=O(dln^2(2d)), where O denotes big-O notation. These bounds are independent of the number of examples and hold for finite or infinite domains. They improve the exponential dependence on d established by Moran and Yehudayoff (2016). The conjecture that O(d) examples suffice remains open. The result is an existence bound on compression size and does not assert a polynomial running time.

The scheme can retain only O(dln(2d)) labels: the remaining retained examples need only be stored without their labels, using the same auxiliary-bit bound (Cai et al. 2026, Remark 1.2). This is a mixture of labeled and unlabeled examples, rather than a wholly unlabeled scheme. The same bounds also admit reconstruction with no more errors on an arbitrary labeled sample than the best member of C on that sample.

Cai et al. (2026) report that the proof was obtained autonomously by the Cogentic multi-agent system using Gemini 4 Carbon; the authors subsequently simplified the proof and take responsibility for its correctness.


See also

Concept Class, Vapnik-Chervonenkis Dimension

Explore with Wolfram|Alpha

References

Cai, Y.; Gupta, V.; Jiang, Y.; Liaw, C.; Mehta, A.; Moran, S.; Velegkas, G.; Wang, D.; and Warmuth, M. K. "Near-Quadratic Sample Compression for All VC Classes." 18 Nov 2026. https://arxiv.org/abs/2611.25011v1.Floyd, S. and Warmuth, M. "Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension." Mach. Learn. 21, 269-304, 1995. https://doi.org/10.1007/BF00993593.Moran, S. and Yehudayoff, A. "Sample Compression Schemes for VC Classes." J. ACM 63, 21, 2016. https://doi.org/10.1145/2890490.

Cite this as:

Weisstein, Eric W. "Sample Compression Scheme." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SampleCompressionScheme.html

Subject classifications