Sample Compression Conjecture (Linear Size in VC Dimension)

Sample Compression Conjecture (Linear Size in VC Dimension)

Definitions and mathematical statement

A concept class $\mathcal C\subseteq\{0,1\}^X$ has VC dimension $d$ when $d$ is the largest size of a set on which all binary labelings occur as restrictions of concepts. A labeled sample is realizable if some $c\in\mathcal C$ agrees with every label. A compression scheme selects a bounded-size labeled subsample and auxiliary information; a reconstruction map must produce a hypothesis consistent with the entire original sample. The target is at most $Cd$ selected examples for an absolute $C$, for every finite-VC class. The side-information alphabet must be fixed with the scheme and independent of sample length; the catalogue does not specify a stronger bit-budget convention. No efficiency or proper-learning requirement is imposed by this combinatorial existence statement.

Formulation and concept references: [S1].

Short English statement

Can every realizable sample from a finite-VC concept class be compressed to only linearly many labeled examples, plus fixed bounded side information, while retaining enough information to reconstruct a consistent hypothesis?

Research attempt

Scope, side information, and process.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, constructs exact compression schemes for finite-support and interval classes, proves a counting lower bound that respects the side-information convention, and tests why finite trace counts do not themselves give reconstruction.

The selected catalogue allows a fixed finite side-information alphabet depending on the scheme, without a prescribed linear bit budget. Source [S1, Definition 2.1] uses a stronger convention counting examples and side bits together. We do not silently impose that stronger requirement. Conversely an alphabet growing with sample length, or an unbounded integer hidden in side information, would violate the selected formulation. The first gap is a universal construction with at most $Cd$ examples for arbitrary finite-VC classes.

Zero dimension and finite concept classes.

Assume the class is nonempty. If its VC dimension is zero, all concepts agree at every point: two concepts disagreeing at one point would shatter that singleton. Thus there is one function as a set-theoretic concept class. The compressor stores nothing and reconstruction returns that function, meeting the bound even when $d=0$. An empty class has no realizable samples and can be treated vacuously.

There is a separate consequence of the allowed side alphabet. If $\mathcal C$ is finite, choose a consistent concept from the finite class and transmit its index as side information, storing no examples. The index alphabet is fixed with the class and independent of the sample length. Therefore a general lower bound on the number of retained examples cannot follow merely by counting the concepts in one finite class.

This observation does not solve the problem for infinite classes of finite VC dimension. The scheme may have only a fixed finite alphabet, so it cannot transmit an arbitrary member of an infinite class as one unrestricted symbol. The distinction is consequential rather than a matter of encoding taste.

A complete size-$d$ scheme for finite supports.

On an infinite domain $X$, let $\mathcal C_d$ consist of the indicators of subsets of size at most $d$. Its VC dimension is exactly $d$: any $d$ points can receive arbitrary labels, while $d+1$ points cannot all be positive.

For a realizable finite sample, retain every positively labeled example. There are at most $d$ distinct positive points. Reconstruct the function equal to one exactly on the retained set. It agrees with all positive examples by construction and with every negative example because a realizable sample cannot give both labels to one point. No side information is needed.

Repeated copies of the same labeled point can be removed before compression. Realizability ensures consistency of their labels, and reconstruction on the distinct sample automatically handles every repetition. This verifies the full sample requirement rather than only the selected examples.

Thresholds and intervals: exact endpoint reconstruction.

For upper thresholds on a linearly ordered infinite domain, retain the least observed positive point, if one exists, and reconstruct the upper ray beginning there. Every observed negative point lies below it in a realizable threshold sample, so reconstruction is consistent. If no positive point occurs, use a fixed side symbol to reconstruct the zero function. Properness is not required; including that function in the class would also be harmless. This gives one-example compression for a VC-one class.

For intervals on $\mathbb R$, retain the least and greatest positive sample points and reconstruct their closed interval. If only one distinct positive point occurs, retain it once and reconstruct a singleton. If none occur, reconstruct the empty set. In a realizable sample, no negative sample point can lie between the extreme positives, since an interval containing those extremes contains everything between them. The resulting hypothesis therefore agrees with the whole sample.

These are extremal-point arguments, not assertions that an arbitrary set of two examples determines a unique consistent interval. Many intervals may fit a sample; the scheme chooses a canonical reconstruction from the stored endpoints.

A size-$2t$ scheme for unions of $t$ intervals.

Sort the distinct sample points by position and split its positive labels into maximal consecutive positive runs, with negative sample points separating successive runs. A sample realizable by a union of at most $t$ intervals has at most $t$ positive runs: each nonempty run requires an interval component that does not cross a separating negative point.

For each positive run retain its first and last point, storing a singleton run only once. This uses at most $2t$ examples. Reconstruction forms the union of the closed intervals corresponding to the recorded pairs, with singletons treated as degenerate intervals.

The compressor also records which ordered retained endpoints form pairs and which are singletons. There are only finitely many such patterns on at most $2t$ ordered points, so this is a fixed finite side alphabet depending on $t$, not on sample length. This detail prevents an ambiguity when adjacent recorded endpoints came from separate singleton runs.

No negative sample point lies inside a reconstructed interval, and every positive sample point belongs to its run's reconstructed interval. Thus the scheme is exactly consistent. The class has VC dimension $2t$: every labeling on $2t$ ordered points has at most $t$ positive runs, while the alternating labeling on $2t+1$ points beginning and ending with one requires $t+1$ runs.

A lower bound that survives fixed side information.

Let a scheme retain at most $k$ labeled examples and use an alphabet of size $B<\infty$. Fix $m$ distinct sample locations. Each realizable labeling of all these locations must be assigned a message whose reconstruction agrees with it. Different labelings cannot share the same compressed message.

For unordered subsamples the number of messages is at most \[ B\sum_{j=0}^k\binom mj2^j. \tag{293.1} \] If order among selected examples is allowed, multiply each term by at most $j!$. This only changes the constant for fixed $k$. Hence the number of realizable labelings on those $m$ points must be $O_{B,k}(m^k)$.

For unions of at most $t$ intervals on $m$ ordered points, the exact number of labelings is \[ \sum_{j=0}^t\binom{m+1}{2j}. \tag{293.2} \] Indeed a labeling with exactly $j$ positive runs is specified by choosing their $2j$ distinct beginning and ending boundaries among the $m+1$ gaps before, between and after the points. The count is a polynomial in $m$ of degree $2t$ with positive leading coefficient. Comparing $293.1$ and $293.2$ as $m\to\infty$ forces $k\ge2t$.

Thus the endpoint scheme is optimal in number of examples even when arbitrarily large but fixed finite side information is allowed. The quantifier $m\to\infty$ on one fixed infinite class is what prevents side information from absorbing the lower bound, unlike the finite-class example.

Why a trace-count bound is not a compression map.

Finite VC dimension bounds how many labelings can occur on each fixed finite set. But counting potential messages is not the same as constructing a single reconstruction map compatible across every possible sample. A message consists of actual selected labeled points and a fixed side symbol; reconstruction sees neither the discarded locations nor their labels.

For a concrete failure of a naive interval rule, suppose the compressor keeps only the first positive point and always reconstructs an upper ray. The sample with a positive point at zero and a negative point at one is realizable by a bounded interval, but that reconstruction labels one positively. Choosing a different ray convention has an analogous sample on the other side. The two-endpoint construction succeeds because it carries the missing boundary information.

More generally, picking a consistent concept using the full sample and then retaining an arbitrary small subsample does not make that concept recoverable. Reconstruction may choose a different concept consistent with the stored points and disagree on omitted ones. A successful scheme needs a coherent selection mechanism, not just existence of a hypothesis before compression.

Verification and outcome.

Finite checks enumerate all labelings on ordered sets up to a fixed size, verify the positive-run count, and reconstruct the entire sample from its stored endpoint pattern. They separately check finite-support compression and the formula $293.2$. No efficiency requirement is added; all lower bounds refer to exact consistency and the fixed finite alphabet convention.

UNRESOLVED. Exact linear-size schemes are established for the displayed classes, with a sharp example-count lower bound for interval unions. The remaining gap is a construction working for every finite-VC class without sample-length-dependent side information. Counting traces alone does not provide it.

Sources

• S1 Formal statement, Abstract. https://arxiv.org/html/2410.13012v1. Formulation source.