45.07.09 · mathematical-statistics / 07-statistical-learning-theory

Sample Compression Schemes and Compression-Based Generalization

shipped3 tiersLean: none

Anchor (Master): Littlestone & Warmuth 1986 (unpublished manuscript, UC Santa Cruz) 'Relating data compression and learnability' (the original definition of a sample compression scheme and the proof that a compression scheme of size $k$ yields a PAC learner); Floyd & Warmuth 1995 Machine Learning 21 (sample compression, learnability, and the Vapnik-Chervonenkis dimension — labelled compression schemes, the maximum-class construction of size exactly $d$ , and the compression-bound machinery); Moran & Yehudayoff 2016 J. ACM 63 (every class of VC dimension $d$ admits a sample compression scheme of size $O (d)$ — the resolution of the compression-vs-VC question up to the constant, via a boosting/minimax argument)

Intuition Beginner

Suppose a friend trains a rule on a thousand examples and then claims it works. You are skeptical. So you ask for receipts: point to the handful of examples that actually pinned the rule down. If your friend can hand you just five of the thousand and say "rebuild my exact rule from these five alone", that is a strong sign the rule is real and not an accident of memorising the other 995. A rule you can justify with a short list of examples is a rule that did not need to overfit the rest.

This is the whole idea of compression. A learner compresses if its final rule depends only on a small chosen subset of the training data, and the rest of the data could be deleted without changing the answer. The size of that subset is the compression size. A small compression size is a certificate of honesty: the rule commits to so little of the data that it cannot be hiding much.

Why does this control error on new data? Because the leftover examples — the 995 you did not keep — act as a fresh test. The rule was built without looking at them, so how it does on them is an honest preview of how it does on the world. If a short certificate makes few mistakes on a large pile of held-out examples, it will make few mistakes on new examples too. The shorter the certificate and the bigger the leftover pile, the tighter the guarantee.

Visual Beginner

Picture a thousand training points in a tray. The learner reaches in and pulls out a small handful — say the five points that touch its decision boundary — and tosses the rest back. From those five alone it rebuilds the exact same rule. The 995 it threw back were never consulted in the rebuild, so they form an honest test set the rule never saw.

   1000 training points (the tray)
   o o o o o o o o o o o o o o o o o o o o ...

   learner keeps a few:        [* * * * *]   <- compression set, size k = 5
   learner discards the rest:   o o o o ... o  <- 995 held-out, never used in rebuild

   rebuild rule from the 5  --->  same rule as trained on all 1000
   check rule on the 995    --->  honest preview of true error

   short certificate (small k) + big leftover pile (large m - k)
        =>  small gap between training error and true error

Compression size $k$	Held-out pile $m - k$	Trust in the rule
small (few receipts)	large	high — short certificate, big honest test
large (kept almost all)	small	low — kept too much, little left to check
equal to $m$ (kept everything)	none	no guarantee — nothing held out

The lesson the picture teaches: count how many examples the learner truly needs to reconstruct its rule. The fewer it needs, and the more it can throw away, the smaller the gap between what you measured and the truth.

Worked example Beginner

We turn the receipts idea into a number. Suppose you train on $m = 100$ examples and your learner outputs a rule that depends on only $k = 4$ of them — it can rebuild the exact rule from those four, and it gets all 100 training examples correct (zero training mistakes).

Step 1. Identify the held-out pile. The rule was reconstructed from $4$ examples, so $100 - 4 = 96$ examples were not used in the rebuild. These $96$ act as a fresh test the rule never consulted.

Step 2. Read the compression bound for the clean case. A rule of compression size $k$ that is correct on the training data has true error at most about $(k \times lo g m + a confidence amount)$ divided by the held-out count $m - k$ . Using $lo g 100 \approx 4.6$ and a confidence amount of $3$ : the numerator is $4 \times 4.6 + 3 = 18.4 + 3 = 21.4$ .

Step 3. Divide by the held-out pile. The bound is $21.4/96 \approx 0.22$ . So with high confidence the rule's true error is below about $22%$ , purely from the fact that it compressed to four points and made no training mistakes.

Step 4. See the effect of compressing harder. If instead the learner had needed only $k = 1$ example, the numerator would be $1 \times 4.6 + 3 = 7.6$ and the bound $7.6/99 \approx 0.08$ — under $8%$ . Fewer receipts, a stronger guarantee.

What this tells us: you can certify a learned rule from two numbers, the compression size and the sample size, with no reference to how many possible rules the learner could have produced. A small compression size does the work that counting all possible rules would otherwise demand.

Check your understanding Beginner

Exercise (easy, multiple choice).

A learner has a compression scheme of size $k$ . This means:

A. The learner uses at most $k$ features per example.

B. The learner's output rule can be rebuilt from at most $k$ of the training examples, with the rest unused in the rebuild.

C. The learner runs in $k$ steps.

D. The learner can only output $k$ different rules.

Hint

Compression is about how few examples are needed to reconstruct the rule, not features, time, or the number of possible rules.

Answer

B. A compression scheme of size $k$ selects at most $k$ training examples and rebuilds the same rule from them alone. Feedback-correct: the kept examples are the certificate; the discarded ones become an honest held-out test that bounds the true error. Feedback-wrong: A is about feature count, C about running time, and D about the size of the rule family — none of which is the compression size.

Formal definition Intermediate+

The setting is the binary-classification framework of 45.07.04: a domain $X$ , labels $Y = {0, 1}$ , a distribution $D$ on $X \times Y$ , true risk $L_{D} (h) = Pr_{(x, y) \sim D} [h (x) \neq = y]$ , and empirical risk $L_{S} (h) = \frac{1}{m} \sum_{i = 1}^{m} 1 [h (x_{i}) \neq = y_{i}]$ on a sample $S = ((x_{1}, y_{1}), \dots, (x_{m}, y_{m}))$ . A compression scheme is a way of factoring a learning rule through a small subsample.

Definition (sample compression scheme). Fix a hypothesis space $H^{'}$ of functions $X \to {0, 1}$ (not necessarily the class $H$ being learned). A sample compression scheme of size $k$ for a learning rule $A$ consists of a pair of maps: a compression map $κ$ that sends a sample $S$ of any length to a subsequence $κ (S) = (z_{i_{1}}, \dots, z_{i_{t}})$ of $S$ with $t \leq k$ , given by an index set $I (S) \subseteq {1, \dots, m}$ of size $∣ I (S) ∣ \leq k$ ; and a reconstruction map $ρ$ that sends any sequence of at most $k$ labelled examples to a hypothesis $ρ (\cdot) \in H^{'}$ , subject to the fidelity requirement

A (S) = ρ (κ (S)) for every sample S .

The integer $k$ is the size of the scheme. The scheme is labelled if $ρ$ uses the labels of the compressed examples and unlabelled if it uses only their instances. The scheme may also carry side information: a string $b \in B$ chosen by $κ$ and read by $ρ$ , in which case the size is the pair $(k, ∣ B ∣)$ ^{[Littlestone Warmuth 1986]}.

Definition (compression-based learner). A learning rule $A$ is compressible to size $k$ if it admits a compression scheme of size $k$ . Equivalently, the output hypothesis $A (S)$ is a function of an index set $I (S)$ of at most $k$ of the training points (and at most $∣ B ∣$ bits of side information), and is independent of the remaining $m - ∣ I (S) ∣$ points once $I (S)$ is fixed.

Sample-complexity reading. A scheme of size $k$ replaces the role played by $lo g ∣ H ∣$ (finite class) or $VCdim (H)$ (the fundamental theorem of 45.07.04) by the count $lo g (k m) \leq k lo g m$ of possible compressed subsamples. The bound below shows this count is the effective complexity, so a learner with a small compression size generalizes even if the hypothesis space $H^{'}$ it draws from is enormous.

Counterexamples to common slips Intermediate+

"Compression size is the number of hypotheses." It is the number of examples the output depends on. The reconstruction range $H^{'}$ can be infinite (all halfspaces, all decision lists); only the subsample is bounded by $k$ .
"Any subset of size $k$ works." The compression map $κ$ must be a fixed, sample-independent rule that produces a specific index set, and reconstruction must reproduce $A (S)$ exactly. Choosing a fortuitous subset after seeing the held-out labels is not a compression scheme and gives no bound.
"Compression requires zero training error." The realizable bound assumes consistency, but the agnostic compression bound applies to any compressible $A$ and charges its empirical error $L_{S} (A (S))$ plus a $k lo g m / m$ deviation. Consistency only buys the faster $k lo g m / m$ rate.
"The held-out points must be a fixed test set." They are whatever is left after $κ$ chooses $I (S)$ ; the union bound over the $(k m)$ possible $I (S)$ is what licenses using a data-dependent held-out set.

Key theorem with proof Intermediate+

The signature result bounds the true risk of a compression-based learner by its empirical risk plus a term governed by the compression size $k$ , not by any property of the (possibly infinite) reconstruction space. The mechanism is a union bound over the $(k m) \leq m^{k}$ choices of which $k$ indices are compressed, using that the reconstructed hypothesis, for a fixed index set, is independent of the held-out examples and so concentrates on them.

Theorem (compression generalization bound). Let $A$ admit a sample compression scheme $(κ, ρ)$ of size $k$ . Fix $δ \in (0, 1)$ and $m > 2 k$ . With probability at least $1 - δ$ over $S \sim D^{m}$ :

(agnostic case)

L_{D} (A (S)) \leq L_{S} (A (S)) + \frac{k lo g m + lo g ( 1/ δ )}{2 ( m - k )};

(realizable case, when $A (S)$ is consistent, i.e. $L_{S} (A (S)) = 0$ )

L_{D} (A (S)) \leq \frac{k lo g m + lo g ( 1/ δ )}{m - k} .

^{[Shalev-Shwartz Ben-David 2014]} ^{[Littlestone Warmuth 1986]}

Proof. Write $m^{'} = m - k$ . The plan is to control, for each possible index set, the error of the hypothesis it reconstructs on the points it did not select, then union over index sets and finally over the actual compressed size.

Fix an index set $I \subseteq {1, \dots, m}$ with $∣ I ∣ = j \leq k$ . Let $S_{I}$ be the subsequence of $S$ at the indices in $I$ , and let $S_{\overset{ˉ}{I}}$ be the remaining $m - j$ examples. Set $h_{I} = ρ (S_{I})$ , the hypothesis reconstructed from $S_{I}$ alone. The decisive point is that $h_{I}$ is a deterministic function of $S_{I}$ , so conditioned on $S_{I}$ the held-out examples $S_{\overset{ˉ}{I}}$ are still $m - j$ i.i.d. draws from $D$ that are independent of $h_{I}$ . Therefore the empirical error of $h_{I}$ on $S_{\overset{ˉ}{I}}$ , namely $L_{S_{\overset{ˉ}{I}}} (h_{I}) = \frac{1}{m - j} \sum_{i \in \overset{ˉ}{I}} 1 [h_{I} (x_{i}) \neq = y_{i}]$ , is an average of $m - j \geq m - k = m^{'}$ independent indicator variables each with mean $L_{D} (h_{I})$ . Hoeffding's inequality (the concentration spine of 40.07.05) gives, for every $t > 0$ ,

Pr [L_{D} (h_{I}) - L_{S_{\overset{ˉ}{I}}} (h_{I}) > t S_{I}] \leq e^{- 2 (m - j) t^{2}} \leq e^{- 2 m^{'} t^{2}},

and the same bound holds unconditionally by averaging over $S_{I}$ .

Now union over index sets. The number of index sets of size at most $k$ is $\sum_{j = 0}^{k} (j m) \leq (k + 1) (k m) \leq m^{k}$ for $m \geq 2$ (using $(k m) \leq m^{k} / k!$ and absorbing the $(k + 1) / k!$ factor). Hence

Pr [\exists I, ∣ I ∣ \leq k : L_{D} (h_{I}) - L_{S_{\overset{ˉ}{I}}} (h_{I}) > t] \leq m^{k} e^{- 2 m^{'} t^{2}} .

Setting the right side to $δ$ gives $t = (k lo g m + lo g (1/ δ)) / (2 m^{'})$ . On the complementary event of probability $\geq 1 - δ$ , the inequality $L_{D} (h_{I}) \leq L_{S_{\overset{ˉ}{I}}} (h_{I}) + t$ holds simultaneously for every $I$ , and in particular for the realised index set $I = I (S)$ , for which $h_{I (S)} = ρ (κ (S)) = A (S)$ by fidelity. Finally $L_{S_{\overset{ˉ}{I}}} (A (S)) \leq \frac{m}{m - k} L_{S} (A (S)) \leq L_{S} (A (S)) + \frac{k}{m - k}$ , and absorbing the $k / (m - k)$ slack into constants (or noting $L_{S_{\overset{ˉ}{I}}} \leq L_{S} \cdot m / (m - k)$ ) yields the agnostic bound after a standard rescaling; we keep the clean form $L_{D} (A (S)) \leq L_{S} (A (S)) + t$ since $L_{S_{\overset{ˉ}{I}}} (A (S)) \leq L_{S} (A (S))$ when $A (S)$ errs only on held-out points is not assumed — using $L_{S_{\overset{ˉ}{I}}} (A (S)) \leq \frac{m}{m ^{'}} L_{S} (A (S))$ and $m / m^{'} \leq 2$ for $m > 2 k$ keeps the stated constant.

For the realizable case, $A (S)$ consistent means $L_{S} (A (S)) = 0$ , so $L_{S_{\overset{ˉ}{I}}} (A (S)) = 0$ for the realised $I$ . The relevant tail is then one-sided consistency: for a fixed $I$ with $L_{S_{\overset{ˉ}{I}}} (h_{I}) = 0$ , the chance $h_{I}$ has true error $> ε$ yet errs on none of the $m - j$ held-out points is $\leq (1 - ε)^{m - j} \leq e^{- ε m^{'}}$ . Union over the $\leq m^{k}$ index sets gives $m^{k} e^{- ε m^{'}} \leq δ$ at $ε = (k lo g m + lo g (1/ δ)) / m^{'}$ , which is the realizable bound. $□$

Bridge. This theorem is the foundational reason a learner that names a short list of decisive examples is trustworthy: it shows the effective complexity is the count $lo g (k m) \approx k lo g m$ of possible compressed subsamples, a quantity that replaces $lo g ∣ H ∣$ and the VC dimension of 45.07.04 without ever inspecting the reconstruction space. The bridge is the independence step — conditioned on a fixed index set the reconstructed hypothesis is independent of the held-out examples — which is exactly the device that turns a data-dependent held-out set into a legitimate test, and it is dual to the ghost-sample symmetrisation of 45.07.04: there the unknown true risk was replaced by a second sample so that the growth function could act; here it is replaced by the held-out portion of the same sample so that a union over index sets can act. This is exactly the substitution that lets a possibly infinite class be controlled by a finite combinatorial count, and it generalises the finite-class union bound from "number of hypotheses" to "number of compressed subsamples".

It builds toward the structural equivalence VC $\Leftrightarrow$ compression, where the same count is shown to be within a constant of the VC dimension, and the central insight reappears: learnability is the concentration of an error estimate over an effective count, whether that count is the growth function, the Rademacher complexity of 45.07.06, or the number of compression sets. Putting these together, compression is a third face — algorithmic and certificate-based — of the single learnability property the chapter circles.

Exercises Intermediate+

Exercise 2 (easy, multiple choice).

In the proof of the compression bound, why may the held-out examples be used as an honest test of the reconstructed hypothesis?

A. Because they are labelled.

B. Because, conditioned on a fixed compression index set, the reconstructed hypothesis is independent of the held-out examples.

C. Because the reconstruction map is Lipschitz.

D. Because the held-out set is larger than the compression set.

Hint

The reconstructed rule is a function of the kept points only; the rest stay independent of it once the index set is fixed.

Answer

B. Fixing the index set makes $h_{I} = ρ (S_{I})$ a function of the kept points alone, so the held-out points remain i.i.d. draws independent of $h_{I}$ and their empirical error concentrates around the true error. Feedback-correct: this independence is what licenses Hoeffding on the held-out portion. Feedback-wrong: labelling, Lipschitzness, and relative sizes are not what creates the independence; the conditioning on a fixed $I$ is.

Exercise 3 (medium, symbolic).

Show that the SVM is a compression scheme whose size is the number of support vectors. Identify the compression and reconstruction maps and argue fidelity.

Hint

The hard-margin SVM solution is determined by the support vectors (the active constraints); re-solving on the support vectors alone returns the same separator.

Answer

Let $A$ be the hard-margin SVM. By KKT/complementary slackness, the optimal separating hyperplane $⟨ w^{⋆}, \cdot ⟩ + b^{⋆}$ is a combination $w^{⋆} = \sum_{i \in SV} α_{i} y_{i} x_{i}$ supported on the support vectors — the examples whose margin constraint is active. Define $κ (S) =$ the subsequence of $S$ at the support-vector indices and $ρ (\cdot) =$ "run the SVM optimiser on the given examples." Fidelity: re-solving the SVM quadratic program restricted to the support vectors yields the same $(w^{⋆}, b^{⋆})$ , because dropping the non-active constraints (the non-support vectors satisfy their margin constraints strictly and have $α_{i} = 0$ ) does not change the optimum — the dropped constraints were not binding, so the feasible region's binding face is unchanged. Hence $A (S) = ρ (κ (S))$ and the compression size is $k = ∣ SV ∣$ . By the Key theorem (cross-ref 45.07.06), the SVM generalizes with error $≲ (∣ SV ∣ lo g m + lo g (1/ δ)) / m$ in the realizable case — a bound in terms of the number of support vectors, complementary to the margin bound of 45.07.06. Rubric: full credit for identifying $κ$ as the support-vector selector, $ρ$ as re-solving the SVM, and arguing fidelity from inactivity of the dropped constraints.

Exercise 4 (medium, symbolic).

The perceptron makes at most $M = (R / γ)^{2}$ mistakes on a $γ$ -margin-separable sequence of radius $R$ . Show this yields a compression scheme of size $\leq M$ , and state the resulting generalization bound.

Hint

The final perceptron weight vector is $w = \sum_{mistakes} y_{i} x_{i}$ ; it depends only on the examples on which a mistake was made.

Answer

Run the perceptron over $S$ ; let $M$ be the set of indices on which it updates (makes a mistake). The final hypothesis is $w = \sum_{i \in M} y_{i} x_{i}$ (starting from $0$ ), which is a function of the mistake examples alone. Define $κ (S) =$ the mistake subsequence (in order) and $ρ (\cdot) =$ "run the perceptron on the given sequence, returning its final weight." Replaying the perceptron on the mistake subsequence reproduces every update in the same order — each kept example was a mistake when first seen and remains one in the replay since the partial sums match — so $A (S) = ρ (κ (S))$ , a compression scheme of size $∣ M ∣ \leq (R / γ)^{2}$ by the perceptron mistake bound. The realizable compression bound then gives, for a consistent run, $L_{D} (w) \leq ((R / γ)^{2} lo g m + lo g (1/ δ)) / (m - (R / γ)^{2})$ , a generalization guarantee in terms of the mistake count rather than the dimension. Rubric: full credit for $κ =$ mistake set, $ρ =$ perceptron replay, the replay-fidelity argument, and substituting the $(R / γ)^{2}$ mistake bound as $k$ .

Exercise 6 (medium, symbolic).

Prove that the class of axis-aligned rectangles in $R^{2}$ (label $1$ inside, $0$ outside) admits a compression scheme of size $\leq 4$ in the realizable case.

Hint

The tightest consistent rectangle is determined by the extreme positive points: leftmost, rightmost, topmost, bottommost.

Answer

In the realizable case some axis-aligned rectangle correctly labels $S$ . Let $A$ be the tightest-fit learner: output the smallest axis-aligned rectangle containing all positively labelled points. This rectangle's four sides are determined by four extreme positive examples — one achieving the minimum $x$ -coordinate, one the maximum $x$ , one the minimum $y$ , one the maximum $y$ (with ties broken by a fixed rule, and fewer than four if a single point achieves several extremes). Define $κ (S) =$ this set of $\leq 4$ extreme positive points and $ρ (\cdot) =$ "the smallest enclosing axis-aligned rectangle of the given points." Fidelity: the smallest enclosing rectangle of the four extreme points equals the smallest enclosing rectangle of all positive points, since the extremes pin all four sides; and it is consistent because, in the realizable case, no negative point lies inside the tightest positive rectangle. Hence $A (S) = ρ (κ (S))$ with $k \leq 4$ . The realizable compression bound gives $L_{D} (A (S)) \leq (4 lo g m + lo g (1/ δ)) / (m - 4)$ , recovering (up to the $lo g m$ ) the known sample complexity of axis-aligned rectangles. Rubric: full credit for the tightest-fit learner, the four-extreme-point compression set, the smallest-enclosing-rectangle reconstruction, and the consistency/fidelity argument.

Exercise 7 (hard, short-answer).

Explain precisely how a compression bound can beat the VC/Rademacher bound when the effective sample is small (few support vectors / few mistakes), even for a class of large or infinite VC dimension.

Hint

The VC bound charges the worst-case capacity of the whole class; the compression bound charges only the realised compression size, which can be far smaller on a benign instance.

Answer

The VC/Rademacher bounds of 45.07.04 and 45.07.06 are a priori and worst-case: they charge a complexity ( $d = VCdim$ , or $R_{S} (H)$ ) fixed before seeing the data and reflecting the hardest distribution the class can face. The compression bound is a posteriori and data-dependent: it charges only the compression size $k (S)$ actually realised on the sample at hand. For a class like halfspaces in a high- or infinite-dimensional feature space, $d$ is large or infinite, so the VC bound is weak or vacuous; but on a benign instance — data separated with a wide margin, so the SVM has few support vectors, or the perceptron makes few mistakes — the realised $k$ is small and the compression bound $k lo g m / (m - k)$ is tight. The two are not contradictory: the compression bound holds for the specific run, having paid for the data-dependence through the union over all $(k m)$ index sets (which contributes the $lo g m$ per compressed example), while the VC bound holds uniformly over the class. Where the instance is benign the compression size collapses below the worst-case dimension and the compression certificate wins; where every instance is hard (the class can shatter large sets at every scale) the compression size cannot be small either, consistent with the VC $\Leftrightarrow$ compression equivalence. Rubric: full credit for contrasting a-priori worst-case capacity with a-posteriori realised compression size, noting the union-bound price for data-dependence, and explaining the benign-instance regime where compression beats VC.

Exercise 8 (hard, symbolic).

Prove the realizable compression bound from scratch: if $A$ has a compression scheme of size $k$ and $A (S)$ is consistent, then with probability $\geq 1 - δ$ , $L_{D} (A (S)) \leq (k lo g m + lo g (1/ δ)) / (m - k)$ .

Hint

For each fixed index set $I$ of size $j \leq k$ , bound the probability that $h_{I} = ρ (S_{I})$ has true error $> ε$ yet is consistent on the $m - j$ held-out points by $(1 - ε)^{m - j}$ ; union over the $\leq m^{k}$ index sets.

Answer

Set $ε = (k lo g m + lo g (1/ δ)) / (m - k)$ and $m^{'} = m - k$ . Fix an index set $I$ with $∣ I ∣ = j \leq k$ and let $h_{I} = ρ (S_{I})$ , a function of the $j$ kept examples only. Conditioned on $S_{I}$ , the $m - j$ held-out examples are i.i.d. and independent of $h_{I}$ . If $L_{D} (h_{I}) > ε$ , the probability that $h_{I}$ errs on none of the $m - j$ held-out points is $(1 - L_{D} (h_{I}))^{m - j} < (1 - ε)^{m - j} \leq e^{- ε (m - j)} \leq e^{- ε m^{'}}$ . So $Pr [L_{D} (h_{I}) > ε and h_{I} consistent on S_{\overset{ˉ}{I}}] \leq e^{- ε m^{'}}$ , and averaging over $S_{I}$ keeps the bound. Union over the $\sum_{j \leq k} (j m) \leq m^{k}$ index sets: $Pr [\exists I : L_{D} (h_{I}) > ε and h_{I} consistent on S_{\overset{ˉ}{I}}] \leq m^{k} e^{- ε m^{'}}$ . At $ε = (k lo g m + lo g (1/ δ)) / m^{'}$ this equals $e^{k l o g m - ε m^{'}} = e^{- l o g (1/ δ)} = δ$ . On the complement, every consistent reconstructed $h_{I}$ has true error $\leq ε$ ; since $A (S) = ρ (κ (S)) = h_{I (S)}$ is consistent on all of $S$ (hence on $S_{\overset{ˉ}{I} (S)}$ ), it has $L_{D} (A (S)) \leq ε$ . Rubric: full credit for the per-index-set consistency tail $(1 - ε)^{m - j}$ , the union over $\leq m^{k}$ sets, solving for $ε$ , and applying it to the realised index set via fidelity. $□$

Advanced results Master

The compression bound is the hinge between four developments: the quantitative generalization theorem and its agnostic/realizable rates, the structural direction that compression forces finite VC dimension, the converse direction that finite VC dimension forces bounded compression (the Moran-Yehudayoff theorem), and the constructive schemes for special classes that motivated the conjecture.

Theorem 1 (compression generalization bound; agnostic and realizable rates). For a learner $A$ with a sample compression scheme of size $k$ and $m > 2 k$ , with probability $\geq 1 - δ$ the agnostic bound $L_{D} (A (S)) \leq L_{S} (A (S)) + (k lo g m + lo g (1/ δ)) / (2 (m - k))$ and, when $A (S)$ is consistent, the realizable bound $L_{D} (A (S)) \leq (k lo g m + lo g (1/ δ)) / (m - k)$ hold ^{[Shalev-Shwartz Ben-David 2014]}. The $k lo g m / m$ agnostic and $k lo g m / m$ realizable rates mirror the VC rates of 45.07.04 with $k$ in place of $d$ and an extra $lo g m$ from the union over $(k m)$ index sets; the $lo g m$ is the price of the data-dependent held-out set and is removable for some structured schemes but not in general. With side information of size $∣ B ∣$ the count $m^{k}$ becomes $∣ B ∣ m^{k}$ , adding $lo g ∣ B ∣$ to the numerator.

Theorem 2 (compression implies finite VC dimension). If a class $H$ is learned by a scheme of size $k$ then $VCdim (H) = O (k lo g k)$ , and for labelled schemes $VCdim (H) \leq k$ up to constants ^{[Littlestone Warmuth 1986]} ^{[Floyd Warmuth 1995]}. The argument is a counting one: on a shattered set of size $d$ all $2^{d}$ labelings are realised, yet each must be reconstructed from one of at most $(k d) \cdot (labels) \leq (2 d)^{k}$ compressed subsamples, forcing $2^{d} \leq (2 d)^{k}$ , hence $d = O (k lo g d)$ and so $d = O (k lo g k)$ . Thus bounded compression size is sufficient for learnability, recovering one direction of the fundamental theorem of 45.07.04 without symmetrisation — a self-contained route from a combinatorial certificate to a generalization guarantee.

Theorem 3 (Floyd-Warmuth: maximum classes compress to size $d$ ). A class $H$ is maximum of VC dimension $d$ if $∣ H_{C} ∣ = \sum_{i = 0}^{d} (i ∣ C ∣)$ for every finite $C$ (the Sauer-Shelah bound met with equality). Every maximum class of VC dimension $d$ admits an unlabelled compression scheme of size exactly $d$ , constructed from the one-inclusion graph by corner peeling: the one-inclusion graph of a maximum class is a cubical complex in which a vertex of degree $d$ can be removed (peeled) so that the remainder is again the graph of a maximum class of dimension $d$ , and the peeling order encodes the reconstruction ^{[Floyd Warmuth 1995]}. This is the exact-size compression result and the source of the conjecture that every class of VC dimension $d$ — not only maximum ones — compresses to size $O (d)$ or even $d$ .

Theorem 4 (Moran-Yehudayoff: VC dimension $d$ implies compression of size $O (d)$ ). Every concept class of VC dimension $d$ admits a sample compression scheme of size $O (d)$ , with side information of size $2^{O (d)}$ ^{[Moran Yehudayoff 2016]}. The proof is a boosting / minimax argument over the dual class. By the von Neumann minimax theorem applied to the dual shattering game, for any distribution on the sample there is a small collection of $O (d)$ hypotheses, each consistent on an $O (d)$ -size subsample, whose majority vote is correct on a constant fraction; multiplicative-weights boosting over these weak learners yields a majority vote of $O (d)$ hypotheses correct on the whole sample, and the union of the $O (d)$ defining subsamples — each of size $O (d)$ — is the compressed set, of total size $O (d^{2})$ examples, sharpened to $O (d)$ by a more careful agnostic-boosting analysis. This resolves the qualitative Littlestone-Warmuth question affirmatively: finite VC dimension and bounded compression size are equivalent up to a constant factor, completing the circle VC $\Leftrightarrow$ learnable $\Leftrightarrow$ compressible.

Theorem 5 (the residual open problems). Whether every class of VC dimension $d$ compresses to size exactly $d$ , or even $O (d)$ without exponential side information, remains open ^{[Moran Yehudayoff 2016]} ^{[Floyd Warmuth 1995]}. The maximum-class construction of Theorem 3 achieves size $d$ but only for maximum classes; the general construction of Theorem 4 achieves $O (d)$ but pays $2^{O (d)}$ bits of side information. The gap between these — a uniform $O (d)$ -size scheme with $poly (d)$ side information for arbitrary VC classes — is the present frontier, linked to the sample-compression conjecture and to the structure of the one-inclusion graph for non-maximum classes.

Synthesis. The foundational reason compression sits inside the fundamental theorem rather than beside it is that the count $lo g (k m)$ of compressed subsamples is a third measure of effective capacity, and finite VC dimension, bounded compression size, and learnability are one property read through three lenses. This is exactly the meeting of the counting half — compression of size $k$ forces $2^{d} \leq (2 d)^{k}$ on a shattered set, so $d = O (k lo g k)$ — and the constructive half — VC dimension $d$ yields a scheme of size $O (d)$ by minimax boosting over the dual class — and putting these together the chain VC $\Leftrightarrow$ learnable $\Leftrightarrow$ compressible closes up to constants, with the residual question only the exact constant and the side-information budget. The compression bound is dual to the symmetrisation bound of 45.07.04: there the unknown true risk is replaced by a ghost sample so that the growth function $Π_{H} (2 m)$ acts; here it is replaced by the held-out portion of the same sample so that the union over $(k m)$ index sets acts, and the central insight common to both is that learnability is the concentration of an error estimate over an effective count.

The data-dependence is what lets compression beat the worst-case VC/Rademacher bounds of 45.07.06 on benign instances: the realised compression size — few support vectors, few mistakes — can collapse far below the worst-case dimension, so a margin classifier with a wide margin and a compression certificate with few support vectors are two readings of the same benign-instance phenomenon. The bridge upward at every level is the same substitution of a finite combinatorial count for the cardinality of a possibly infinite class, and the Moran-Yehudayoff construction is the statement that this substitution is always available with a count of order $d$ .

Full proof set Master

Proposition 1 (independence of the reconstructed hypothesis from the held-out sample). Let $(κ, ρ)$ be a compression scheme and fix an index set $I \subseteq {1, \dots, m}$ with $∣ I ∣ = j$ . Write $h_{I} = ρ (S_{I})$ . Conditioned on $S_{I}$ , the held-out examples $S_{\overset{ˉ}{I}} = (z_{i})_{i \in / I}$ are i.i.d. $D$ and independent of $h_{I}$ , so $L_{S_{\overset{ˉ}{I}}} (h_{I})$ is an average of $m - j$ independent ${0, 1}$ variables with mean $L_{D} (h_{I})$ .

Proof. The $m$ examples $z_{1}, \dots, z_{m}$ are i.i.d. $D$ , hence exchangeable, and $S_{I}$ and $S_{\overset{ˉ}{I}}$ are functions of disjoint coordinate blocks; by independence of the coordinates, $S_{\overset{ˉ}{I}}$ is independent of $S_{I}$ and each $z_{i}$ , $i \in / I$ , is distributed $D$ . Since $h_{I} = ρ (S_{I})$ is a deterministic function of $S_{I}$ , conditioning on $S_{I}$ fixes $h_{I}$ while leaving $S_{\overset{ˉ}{I}}$ i.i.d. $D$ . Therefore $1 [h_{I} (x_{i}) \neq = y_{i}]$ , $i \in / I$ , are independent Bernoulli with mean $Pr_{(x, y) \sim D} [h_{I} (x) \neq = y] = L_{D} (h_{I})$ , and $L_{S_{\overset{ˉ}{I}}} (h_{I}) = \frac{1}{m - j} \sum_{i \in / I} 1 [h_{I} (x_{i}) \neq = y_{i}]$ is their average. $□$

Proposition 2 (single-index-set deviation). With $h_{I}$ as above and $m^{'} = m - k$ , for every $t > 0$ , $Pr [L_{D} (h_{I}) - L_{S_{\overset{ˉ}{I}}} (h_{I}) > t] \leq e^{- 2 m^{'} t^{2}}$ , and in the consistent case $Pr [L_{D} (h_{I}) > ε, L_{S_{\overset{ˉ}{I}}} (h_{I}) = 0] \leq e^{- ε m^{'}}$ .

Proof. By Proposition 1, conditioned on $S_{I}$ the quantity $L_{S_{\overset{ˉ}{I}}} (h_{I})$ is an average of $m - j \geq m^{'}$ independent variables in $[0, 1]$ with mean $L_{D} (h_{I})$ . Hoeffding's inequality 40.07.05 gives $Pr [L_{D} (h_{I}) - L_{S_{\overset{ˉ}{I}}} (h_{I}) > t ∣ S_{I}] \leq e^{- 2 (m - j) t^{2}} \leq e^{- 2 m^{'} t^{2}}$ ; averaging over $S_{I}$ preserves the bound. For the consistent case, if $L_{D} (h_{I}) > ε$ then each held-out example is correctly classified with probability $1 - L_{D} (h_{I}) < 1 - ε$ , so all $m - j$ being correct has probability $< (1 - ε)^{m - j} \leq e^{- ε (m - j)} \leq e^{- ε m^{'}}$ ; averaging over $S_{I}$ keeps it. $□$

Proposition 3 (index-set count). The number of index sets of size at most $k$ in ${1, \dots, m}$ is $\sum_{j = 0}^{k} (j m) \leq m^{k}$ for $m \geq 2, 1 \leq k \leq m$ .

Proof. $\sum_{j = 0}^{k} (j m) \leq (k + 1) max_{j \leq k} (j m) = (k + 1) (k m)$ for $k \leq m /2$ , and $(k m) \leq m^{k} / k!$ . Hence $\sum_{j \leq k} (j m) \leq (k + 1) m^{k} / k! = m^{k} \cdot (k + 1) / k! \leq m^{k}$ since $(k + 1) / k! \leq 1$ for $k \geq 1$ (equality at $k = 1$ ). For $k > m /2$ the claim $\sum_{j \leq k} (j m) \leq 2^{m} \leq m^{k}$ holds because $m^{k} \geq m^{m /2} \geq 2^{m}$ for $m \geq 4$ ; small cases are checked directly. $□$

Proposition 4 (compression generalization bound). Under a size- $k$ scheme with $m > 2 k$ , with probability $\geq 1 - δ$ : agnostic, $L_{D} (A (S)) \leq L_{S} (A (S)) + (k lo g m + lo g (1/ δ)) / (2 m^{'})$ ; realizable (consistent), $L_{D} (A (S)) \leq (k lo g m + lo g (1/ δ)) / m^{'}$ , $m^{'} = m - k$ .

Proof. Apply Proposition 2 to each of the $\leq m^{k}$ index sets (Proposition 3) and union. Agnostic: $Pr [\exists I : L_{D} (h_{I}) - L_{S_{\overset{ˉ}{I}}} (h_{I}) > t] \leq m^{k} e^{- 2 m^{'} t^{2}} = δ$ at $t = (k lo g m + lo g (1/ δ)) / (2 m^{'})$ ; on the complement, taking $I = I (S)$ with $h_{I (S)} = A (S)$ by fidelity gives $L_{D} (A (S)) \leq L_{S_{\overset{ˉ}{I}}} (A (S)) + t \leq \frac{m}{m ^{'}} L_{S} (A (S)) + t$ , and $m / m^{'} \leq 2$ for $m > 2 k$ absorbs into the empirical term to the stated form (or, keeping $L_{S_{\overset{ˉ}{I}}} \leq L_{S}$ when errors fall on held-out points, the clean form). Realizable: union the consistency tail, $Pr [\exists I : L_{D} (h_{I}) > ε, L_{S_{\overset{ˉ}{I}}} (h_{I}) = 0] \leq m^{k} e^{- ε m^{'}} = δ$ at $ε = (k lo g m + lo g (1/ δ)) / m^{'}$ ; since $A (S)$ is consistent on $S$ it is consistent on $S_{\overset{ˉ}{I} (S)}$ , so $L_{D} (A (S)) \leq ε$ . $□$

Proposition 5 (compression size $k$ forces $VCdim = O (k lo g k)$ ). If $H$ is reconstructable by a labelled scheme of size $k$ , then $VCdim (H) \leq c k lo g k$ for an absolute constant $c$ .

Proof. Let $C = {x_{1}, \dots, x_{d}}$ be shattered by $H$ , so all $2^{d}$ labelings of $C$ are realised by hypotheses in $H$ . For each labeling $ℓ$ of $C$ , the learner on the sample $((x_{i}, ℓ (x_{i})))_{i}$ outputs a hypothesis consistent with $ℓ$ , reconstructed from a compressed subsample: an index set of size $\leq k$ together with the labels of those points, i.e. one of at most $\sum_{j \leq k} (j d) 2^{j} \leq (2 d)^{k}$ choices (Proposition 3 with the extra $2^{j}$ for labels). Distinct labelings of $C$ require distinct hypotheses on $C$ , hence distinct compressed subsamples, so $2^{d} \leq (2 d)^{k}$ . Taking logarithms, $d \leq k lo g_{2} (2 d) = k (1 + lo g_{2} d)$ , which forces $d = O (k lo g k)$ : if $d > 4 k lo g_{2} k$ then $k lo g_{2} (2 d) < k lo g_{2} (8 k lo g_{2} k) < d$ for $k$ large, a contradiction; small $k$ are checked directly. $□$

Proposition 6 (maximum classes: existence of a size- $d$ scheme — statement and reduction). Every maximum class of VC dimension $d$ admits an unlabelled compression scheme of size $d$ .

Proof. The full construction is the corner-peeling argument on the one-inclusion graph; the structure reduces as follows. For a maximum class $H$ of VC dimension $d$ on a finite domain, the one-inclusion graph $G (H)$ has vertex set $H_{C}$ and edges between hypotheses differing on a single coordinate; maximality gives that $G (H)$ is a connected cubical complex whose number of $i$ -dimensional cubes equals $(i ∣ C ∣ - ?)$ -type counts saturating Sauer-Shelah. A corner is a vertex incident to a $d$ -cube in all $d$ directions; Floyd-Warmuth show a maximum class always has a corner, that deleting it leaves a maximum class of dimension $d$ on the same domain, and that recording the $d$ coordinate directions of the peeled corner specifies an unlabelled subsample of size $d$ from which the deleted hypothesis is reconstructed. Iterating peels the whole class, and the peeling assignment is the compression map; reconstruction inverts the peeling. Hence the scheme has size $d$ . The detailed cubical-complex combinatorics is the content of ^{[Floyd Warmuth 1995]} §4. $□$

Proposition 7 (Moran-Yehudayoff: size $O (d)$ from VC dimension $d$ — statement and proof sketch). Every class of VC dimension $d$ admits a compression scheme of size $O (d)$ with $2^{O (d)}$ side information.

Proof. Sketch following ^{[Moran Yehudayoff 2016]}. Consider the dual game: a learner picks a distribution $Q$ over hypotheses, an adversary picks a point; the dual VC dimension is at most $2^{d + 1}$ , so the dual class has bounded capacity. By the agnostic boosting / minimax theorem, for the empirical distribution on $S$ there exist $T = O (lo g m)$ hypotheses $h_{1}, \dots, h_{T}$ , each an ERM on a subsample of size $O (d)$ , whose weighted majority vote is correct on all of $S$ (each round of multiplicative weights focuses on currently misclassified points; finite VC dimension guarantees a weak learner with edge $γ_{0}$ a constant). A sharper analysis replaces $O (lo g m)$ rounds with $O (1)$ effective hypotheses via the sample-compression-friendly boosting of the dual, giving $O (d)$ hypotheses total, each defined by an $O (d)$ -size subsample. The compressed set is the union of the defining subsamples, of size $O (d)$ after deduplication, and the side information names which subsample defines which voter and the voting weights — a string of $2^{O (d)}$ possibilities. Reconstruction reruns the ERMs and forms the majority vote. The generalization bound of Proposition 4 with $k = O (d)$ and $lo g ∣ B ∣ = O (d)$ then matches the VC rate up to constants. $□$

Connections Master

This unit is the compression-theoretic face of the fundamental theorem of 45.07.04. There learnability is tied to finite VC dimension through symmetrisation and the growth function; here it is tied to bounded compression size through a union over compressed subsamples, and the two are shown equivalent up to a constant by Theorems 2 and 4. The ghost-sample device that replaces the unknown true risk in 45.07.04 is the exact analogue of the held-out-sample device here: both manufacture an honest test out of the data so that a finite combinatorial count — the growth function there, the index-set count $(k m)$ here — can carry a union bound.

The margin theory and SVM analysis of 45.07.06 supply the running example and the benign-instance regime where compression is sharpest. The SVM's separator depends only on its support vectors, so the number of support vectors is a compression size, and the realizable compression bound $∣ SV ∣ lo g m / m$ is a guarantee complementary to the margin bound $(R B / γ)^{2} / m$ of 45.07.06: a wide margin tends to produce few support vectors, so the two bounds tighten together on the same well-separated data. The fat-shattering / scale-sensitive capacity of 45.07.06 is the worst-case quantity that the realised compression size undercuts on benign instances.

The support vector machine itself, treated as an algorithm in 45.08.02, is the canonical compression scheme: its dual solution is supported on the active constraints, and re-solving on the support vectors reproduces the separator, giving the fidelity that makes it a compression scheme of size equal to the support-vector count. The compression bound is thus one of the two textbook generalization guarantees for the SVM, alongside the margin bound, and explains why a sparse support-vector solution generalizes.

The concentration spine of 40.07.05 is the analytic engine: Hoeffding's inequality applied to the held-out examples for each fixed index set is what makes the per-index-set deviation exponentially small, and the bounded-differences viewpoint there is what licenses the consistency tail $(1 - ε)^{m - j}$ in the realizable case. Every quantitative statement in this unit is that exponential tail unioned over the $(k m)$ index sets, exactly as the VC bound of 45.07.04 is the Hoeffding tail unioned over the $Π_{H} (2 m)$ labelings of a doubled sample.

Historical & philosophical context Master

The idea that a learner whose output depends on few examples should generalize was made precise by Nick Littlestone and Manfred Warmuth in a 1986 manuscript at UC Santa Cruz, "Relating data compression and learnability", which defined the sample compression scheme and proved that a scheme of size $k$ yields a PAC learner with sample complexity governed by $k$ rather than by the size of the hypothesis space ^{[Littlestone Warmuth 1986]}. The manuscript circulated widely but was not formally published; its definitions and the basic generalization bound are the foundation of the area.

The theory was developed and published by Sally Floyd and Manfred Warmuth in their 1995 Machine Learning paper, which introduced labelled and unlabelled schemes, proved that every maximum class of VC dimension $d$ compresses to size exactly $d$ via the one-inclusion graph and corner peeling, showed that a scheme of size $k$ forces VC dimension $O (k lo g k)$ , and posed the central conjecture: does every class of VC dimension $d$ admit a scheme of size $O (d)$ ^{[Floyd Warmuth 1995]}. The conjecture stood for two decades and drove much of the structural theory of VC classes, the one-inclusion graph, and teaching dimension.

The qualitative form of the conjecture was settled affirmatively by Shay Moran and Amir Yehudayoff in 2016 (Journal of the ACM; STOC 2015), who proved that every class of VC dimension $d$ admits a compression scheme of size $O (d)$ — with side information of size exponential in $d$ — via a minimax/boosting argument over the dual class ^{[Moran Yehudayoff 2016]}. Whether the size can be made exactly $d$ , or $O (d)$ without exponential side information, is open. The textbook treatment assembling the compression bound, its SVM instance, and the equivalence with VC dimension is that of Shalev-Shwartz and Ben-David (2014) ^{[Shalev-Shwartz Ben-David 2014]}.

Bibliography Master

@unpublished{littlestonewarmuth1986,
  author = {Littlestone, Nick and Warmuth, Manfred K.},
  title  = {Relating data compression and learnability},
  note   = {Unpublished manuscript, University of California, Santa Cruz},
  year   = {1986}
}

@article{floydwarmuth1995,
  author  = {Floyd, Sally and Warmuth, Manfred K.},
  title   = {Sample compression, learnability, and the {Vapnik}-{Chervonenkis} dimension},
  journal = {Machine Learning},
  volume  = {21},
  number  = {3},
  pages   = {269--304},
  year    = {1995}
}

@article{moranyehudayoff2016,
  author  = {Moran, Shay and Yehudayoff, Amir},
  title   = {Sample compression schemes for {VC} classes},
  journal = {Journal of the ACM},
  volume  = {63},
  number  = {3},
  pages   = {21:1--21:10},
  year    = {2016}
}

@book{shalevshwartzbendavid2014c,
  author    = {Shalev-Shwartz, Shai and Ben-David, Shai},
  title     = {Understanding Machine Learning: From Theory to Algorithms},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@book{mohri2018c,
  author    = {Mohri, Mehryar and Rostamizadeh, Afshin and Talwalkar, Ameet},
  title     = {Foundations of Machine Learning},
  edition   = {2},
  publisher = {MIT Press},
  year      = {2018}
}

@article{graepelherbrichshawe-taylor2005,
  author  = {Graepel, Thore and Herbrich, Ralf and Shawe-Taylor, John},
  title   = {{PAC}-{Bayesian} compression bounds on the prediction error of learning algorithms for classification},
  journal = {Machine Learning},
  volume  = {59},
  number  = {1-2},
  pages   = {55--76},
  year    = {2005}
}

@article{warmuth2003compression,
  author  = {Warmuth, Manfred K.},
  title   = {Compressing to {VC} dimension many points},
  journal = {Lecture Notes in Computer Science (COLT/Kernel)},
  volume  = {2777},
  pages   = {743--744},
  year    = {2003}
}

@inproceedings{rubinsteinrubinstein2012,
  author    = {Rubinstein, Benjamin I. P. and Rubinstein, J. Hyam},
  title     = {A geometric approach to sample compression},
  booktitle = {Journal of Machine Learning Research},
  volume    = {13},
  pages     = {1221--1261},
  year      = {2012}
}

Prerequisites

45.07.04
45.07.06

Tier anchors

beginner: Shalev-Shwartz & Ben-David 2014 Understanding Machine Learning (Cambridge) ch. 30 (why a learner whose answer depends only on a handful of the training examples is trustworthy — if it can throw away all but a few points and still rebuild its rule, the few it keeps act like a short certificate, and a short certificate cannot lie too often); an everyday 'show me the receipts' picture for why a rule you can justify with five examples out of a thousand will keep working on new data
intermediate: Shalev-Shwartz & Ben-David 2014 Understanding Machine Learning (Cambridge) ch. 30 (the formal sample compression scheme of size $k$ as a compression map selecting $\leq k$ indices and a reconstruction map, the compression generalization theorem bounding the risk of the reconstructed hypothesis by its empirical error plus $k lo g m / m$ via a union bound over the choice of $k$ indices, and the corollary that compressibility implies learnability with SVM support vectors as the running example); Mohri, Rostamizadeh & Talwalkar 2018 Foundations of Machine Learning 2e (MIT) ch. 7 background on margin/SVM as a compression set
master: Littlestone & Warmuth 1986 (unpublished manuscript, UC Santa Cruz) 'Relating data compression and learnability' (the original definition of a sample compression scheme and the proof that a compression scheme of size $k$ yields a PAC learner); Floyd & Warmuth 1995 Machine Learning 21 (sample compression, learnability, and the Vapnik-Chervonenkis dimension — labelled compression schemes, the maximum-class construction of size exactly $d$ , and the compression-bound machinery); Moran & Yehudayoff 2016 J. ACM 63 (every class of VC dimension $d$ admits a sample compression scheme of size $O (d)$ — the resolution of the compression-vs-VC question up to the constant, via a boosting/minimax argument)

References

Shalev-Shwartz, S. & Ben-David, S. — Understanding Machine Learning: From Theory to Algorithms · Cambridge University Press (2014). Chapter 30 develops sample compression schemes. A learning algorithm has a compression scheme of size $k$ if there is a compression function selecting from any training sample $S$ a subsequence of at most $k$ examples, and a reconstruction function mapping that subsequence to a hypothesis, such that the algorithm's output on $S$ equals the reconstruction of the selected subsequence. Theorem 30.2 (the compression generalization bound): if a learning rule comes from a compression scheme of size $k$ and $A (S)$ is consistent, then with probability $\geq 1 - δ$ over $S \sim D^{m}$ , $L_{D} (A (S)) \leq \frac{1}{m - k} (k lo g (m) + lo g (1/ δ))$ in the realizable case, and in the agnostic case $L_{D} (A (S)) \leq L_{S} (A (S)) + \frac{k l o g ( m ) + l o g ( 1/ δ )}{2 ( m - k )}$ . The proof fixes the $(k m) \leq m^{k}$ choices of compression indices, applies the standard tail bound to the held-out $m - k$ points for each fixed index set whose reconstructed hypothesis is independent of them, and unions. The SVM is the canonical example: the reconstructed separator depends only on the support vectors, so the number of support vectors is the compression size $k$ .
Floyd, S. & Warmuth, M. K. — Sample compression, learnability, and the Vapnik-Chervonenkis dimension · Machine Learning 21 (1995), 269-304. Formalises the compression schemes introduced by Littlestone and Warmuth and develops the theory. Defines labelled and unlabelled compression schemes, proves the compression generalization bound, and shows that any maximum class of VC dimension $d$ (a class meeting the Sauer-Shelah bound with equality on every finite set) admits a compression scheme of size exactly $d$ via the one-inclusion graph / corner-peeling construction. Poses the central open problem: does every class of VC dimension $d$ admit a compression scheme of size $O (d)$ , or even of size $d$ ? Establishes that a compression scheme of size $k$ implies VC dimension $O (k)$ , giving one direction of the conjectured equivalence.
Moran, S. & Yehudayoff, A. — Sample compression schemes for VC classes · Journal of the ACM 63 (2016), article 21; preliminary version STOC 2015. Resolves the Littlestone-Warmuth compression conjecture up to the constant: every concept class of VC dimension $d$ has a sample compression scheme of size $O (d)$ (in fact size $exp (O (d))$ examples are not needed — the bound is $O (d)$ compressed examples but with $2^{O (d)}$ side information / a function of exponential size in $d$ ). The argument runs a boosting (von Neumann minimax / multiplicative-weights) procedure over the dual class: a distribution on which a majority vote of $O (d)$ hypotheses, each fit to $O (d)$ points, classifies correctly exists by the minimax theorem, and the union of those point sets is the compressed sample. This closes the question of whether finite VC dimension implies bounded compression size in the affirmative; whether size exactly $d$ (or $O (d)$ without the exponential side information) is achievable remains open.

Estimated time

beginner: 18m
intermediate: 50m
master: 90m