Near-Quadratic Sample Compression for All VC Classes

Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang, Manfred K. WarmutharXiv 2026 · arXiv

This paper achieves a major breakthrough in learning theory by resolving a decades-old open question: the polynomial version of the Sample Compression Conjecture. The authors prove that any concept class with Vapnik–Chervonenkis (VC) dimension $d$ can be compressed into a subset of just $O(d^2 \log^2 d)$ examples, providing the first polynomial bound and a massive improvement over the previous best exponential bound.

TL;DR

For 40 years, researchers wondered if "learnability" (VC dimension $d$) implies that a model can always be represented by a small, polynomial-sized subset of its training data. This paper finally proves it is possible, constructing a sample compression scheme of size $O(d^2 \log^2 d)$, moving us significantly closer to the ultimate goal of a linear $O(d)$ bound.

What Problem Does This Paper Address?

In machine learning, generalization is the ability to predict outcomes for new data, while simplification is the ability to explain observations using very little information. These are linked by Occam’s Razor: simpler explanations tend to generalize better.

Sample compression schemes formalize this. Imagine a game between a "compressor" and a "reconstructor." The compressor takes a large labeled dataset and picks a tiny subset of examples (the "compression") and a few bits of side information. The reconstructor must then use only that tiny subset to recover a hypothesis that is perfectly consistent with the entire original dataset.

Figure 2: A sample compression scheme. The reconstructed concept is consistent with the entire sample, not only the retained examples.

The Sample Compression Conjecture, posed in the 1980s and 90s, asserts that if a concept class has VC dimension $d$, it should be compressible to size $O(d)$. While simple classes like axis-aligned rectangles (shown below) were known to be compressible to size $O(d)$, the best general bound for all VC classes remained stuck at $2^{O(d)}$—an exponential gap that has frustrated theorists for years.

Figure 1: Compression for axis-aligned rectangles. The compressor retains the circled positive examples T, at most one for each side. The reconstructor outputs the smallest axis-aligned rectangle containing T. For a sample realizable by an axis-aligned rectangle, this rectangle contains every positive example and excludes every negative example.

Methods

The authors' approach is built on reconstructing a weighted majority vote of concepts. If you have a pool of predictors that, on average, get the answer right more than half the time for every point in your sample, you can combine them into a single, perfectly consistent predictor.

The technical challenge is finding a small "pool" of concepts. The authors use three key pillars:

  1. Unlabeled Anchors: They use unlabeled examples to partition the space of all possible concepts into "cells." Concepts in the same cell behave identically on those unlabeled points. They then pick one "representative" concept from each cell.
  2. Iterative Refinement & Entropy: They start with a single cell and iteratively add unlabeled examples to split cells further. They track progress using Shannon entropy. They prove that each round of adding examples either finds a good enough set of representatives or increases the entropy of the partition by a constant amount.
  3. Game Theory (Maximal Lotteries): To decide how to shift "mass" between concepts and refine cells, they frame the problem as a zero-sum game. Using Linear Programming (LP) duality, they identify which points in the sample are the most "informative" to add to the compression set.
Figure 3: The black dots represent linear classifiers as points in the dual space. The blue dots mark the representatives of the occupied cells. On the left, the line corresponding to one unlabeled example separates classifiers that label it 0 from those that label it 1. On the right, a second unlabeled example adds a line that refines the partition.

Datasets

As a theoretical work in mathematical learning theory, this paper does not use empirical datasets. The results are proven mathematically to hold for any concept class with a finite VC dimension.

Key Insights and Ideas

  • Bypassing the Dual VC Dimension: Previous attempts were often limited by the "dual" VC dimension, which can be exponentially larger than the standard VC dimension. This paper avoids that trap by using unlabeled examples to anchor the concept pool.
  • Entropy as a Progress Bar: By showing that cell-mass entropy must increase steadily, the authors can guarantee that the refinement process terminates quickly (within $O(d \log d)$ rounds).
  • The Power of Unlabeled Data: Interestingly, the bulk of the compression size ($O(d^2 \log^2 d)$) comes from unlabeled points used to define the concept pool, while the number of labeled points needed is much smaller ($O(d \log d)$).
  • AI-Assisted Discovery: In a fascinating meta-commentary, the authors disclose that the core proof was obtained autonomously by a multi-agent orchestration (Cogentic) running on Gemini 4 Carbon. The AI iteratively improved the bound from $O(d^{16})$ down to the final near-quadratic result.

Key Results

The paper proves that for any concept class of VC dimension $d$:

  • Compression Size: A labeled sample compression scheme exists with size $k = O(d^2 \log^2 d)$ examples.
  • Side Information: The scheme requires only $b = O(d \log^2 d)$ bits of side information.
  • Agnostic Compression: The result also implies the existence of polynomial-sized compression schemes for the "agnostic" setting (where the data might be noisy or not perfectly fit the class).

This is the first time any polynomial bound has been established for general VC classes, resolving the "weak" version of the conjecture.

Limitations and Future Work

The primary limitation is the gap between $O(d^2 \log^2 d)$ and the conjectured $O(d)$. While near-quadratic is a massive leap from exponential, the "holy grail" of a linear bound remains open.

Additionally, the proof focuses on the existence of these schemes. While the MWU and LP components are algorithmic, the paper does not focus on the computational efficiency of finding the optimal compression for a given sample in practice. The authors suggest that their "entropy-gain" framework might eventually be refined to reach the elusive $O(d)$ goal.

Summary updated

Abstract

The sample compression conjecture is a longstanding open problem in learning theory, originating in the work of Littlestone and Warmuth in the 1980s. At its heart is a connection between simplification and generalization: if a predictor consistent with a training sample is defined using only a small part of that sample, then it is likely to generalize. Sample compression schemes formalize this idea, and many natural learning algorithms can be analyzed this way. The sample compression conjecture of Floyd and Warmuth (1995) asserts that every binary concept class of VC dimension $d$ admits a sample compression scheme of size $O(d)$; a weaker conjecture asks only for size polynomial in $d$. Both have remained open: the first bound depending only on $d$, due to Moran and Yehudayoff (2016), is exponential in $d$. We prove the weaker conjecture by constructing a sample compression scheme of size $O(d^2 \log^2 d)$.
BibTeX
@misc{cai2026near,
  author = {Yang Cai and Vineet Gupta and Yanchen Jiang and Christopher Liaw and Aranyak Mehta and Shay Moran and Grigoris Velegkas and Di Wang and Manfred K. Warmuth},
  title = {{Near-Quadratic Sample Compression for All VC Classes}},
  year = {2026},
  eprint = {2611.25011},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25011},
}
Figure