A short explanation of the sample
A classifier can fit a sample simply because its hypothesis class is flexible. A different possibility is that the classifier can be reconstructed from a small part of the sample. If so, most observations were not needed to specify it; they can serve as a check on a hypothesis determined by the retained observations. This idea leads to a generalization bound even when the full hypothesis class is infinite.
The retained observations are chosen after seeing the data, so they cannot be treated as a fresh random training set and the rest as an automatically independent test set. The proof must account for every possible choice of retained indices and every possible side message. That accounting is the main mathematical cost of data-dependent compression.
A precise compression model
Let be a distribution on labeled examples , and take an i.i.d. sample from . For a classifier , write . Assume all classifiers produced by the reconstruction rule are measurable and the selection, loss and risk events used below are measurable.
Definition 4.1.1
(Compression scheme with side information)
A deterministic compression procedure selects a subset of at most indices, together with exactly side-information bits. A fixed deterministic reconstruction rule receives only the selected labeled examples, in increasing index order, and those bits; it returns a classifier . It does not receive the remaining observations. The side string may depend on the entire sample, so the proof will count all possibilities. If no side information is needed, take .
Assume that, with probability one over , the final reconstructed classifier is consistent with all examples. This can be guaranteed, for example, by a realizable sampling model and a compression scheme constructed for that model. The theorem does not say that such a scheme exists for every distribution or class. Repeated sample values are allowed: the selection is by positions, and the binomial count refers to positions rather than distinct values.
The compression bound
Theorem 4.1.2
(Consistent compression with finite side information)
Let and be integers. Under the model above, for every , with probability at least the reconstructed classifier satisfies
Logarithms are natural. The bound may exceed one, in which case it remains true but uninformative.
Concept lensCombinatorial
The bound counts descriptions
A description is a pair: a set of at most positions and a -bit string. There are of them, so the bound reads . For , we get , , and with the bound is .
Proof
(Counting every possible retained set and side string)
For , fix a set of positions of size and fix a particular -bit side string. Condition on the examples at those positions. The reconstruction rule now produces a fixed classifier ; the other examples remain independent draws from . If , the conditional probability that all remaining examples agree with is at most
This bound is uniform in the retained values. There are possible index sets of size and side strings. A union bound over all , index sets and strings therefore bounds the probability that any such reconstruction has true error greater than and agrees with all unretained examples by
The actual compressor may choose its indices and side bits using the whole sample; its output is among the counted possibilities. Full-sample consistency ensures that it agrees with the unretained examples. Setting the last expression to proves the claim when its resulting threshold is below one; if that threshold is at least one, the claim is immediate because risk is at most one.
Proof X-ray
Why a data-dependent choice can still be counted
The independence hypothesis is used in exactly one place: for a fixed index set and side string, conditioning on the selected values leaves the other examples independent draws from , which gives the factor . The actual selection need not be independent of those other examples. The key move is therefore to apply the union bound over every possible selection and side string before asking which one the compressor chose. The consistency hypothesis closes the argument: it guarantees that whichever reconstruction was actually produced is among the counted ones that agree with all unretained examples. The factor rather than appears because the retained examples may be fitted for free, so only the worst case matters. Omitting the count would treat a data-dependent holdout as though it were fixed in advance.
Worked example 4.1.3
(Evaluating the compression bound)
For , , , and , the index count is . The bound is
This is a sufficient high-probability bound, not an exact risk for a particular run. The sum over index sets is a proof cost: the reconstruction rule itself receives the retained examples and bits, not a separate description of all those possible sets. For a small sample the same formula says little. With , , and the index count is and the bound is , which exceeds one: the statement remains true, but no information about the risk can be drawn from it.
A threshold scheme with two retained examples
Proposition 4.1.4
(Thresholds compress to two examples and two bits)
Let the classifiers be on together with the two constant classifiers, and suppose is realizable by this class: some in it satisfies . Then, almost surely, the sample admits a compression scheme with and whose reconstruction is consistent with all examples. The theorem above therefore applies when .
Proof
(Largest negative and smallest positive)
Every finite sample is consistent with almost surely. If both labels occur, select the largest observed negative point and the smallest observed positive point ; when an extremal value appears at multiple positions, select the smallest index. Consistency with implies : if , every negative lies below and every positive lies at or above . Reconstruct with . Every observed negative is at most and every observed positive is at least , so the reconstruction is consistent.
If all labels are zero, retain no point and reconstruct the constant-zero classifier; if all labels are one, reconstruct constant one. Two fixed side bits distinguish these cases and the mixed case. It is not claimed that this is the most economical encoding. Even though there are infinitely many thresholds, the theorem applies to the compressed reconstruction. A sample with both labels in the wrong order is not consistent with this class, so the consistency assumption must not be silently dropped.
Worked example 4.1.5
(Reconstructing a threshold from six labeled points)
Take the sample , , , , , in positions to . The largest negative point is at position 1. The smallest positive point is , which occurs at positions 3 and 6; the rule takes the smallest index, position 3. The retained pair is and , with a side string recording that both labels occur. The reconstruction is . All three negatives, at , and , lie below , and all three positives, at , and , lie above it, so is consistent. The repeated values show why the count refers to positions: the two copies of are different positions, and only one is retained.
Worked example 4.1.6
(The one-label edge case)
Suppose all labels are zero, say at the points . The scheme retains no example, so , and the side string states that the all-zero case occurred. The reconstruction is the constant-zero classifier, consistent with all four examples. The bound for , and is , vacuous, because is tiny. The counting still covers this case: the actual compressor chose , which is among the counted .
Counterexample mode
An empty description cannot use hidden sample information
Let be uniform and let all true labels be zero. Consider the rule that, after seeing the sample, outputs zero on every observed point and one on every unobserved point. Its empirical error is zero, while at least domain points are unobserved, so its true error is at least . Calling its description “zero retained examples and zero bits” would be invalid: reconstruction needs the full list of observed points. A compression bound with cannot be applied when that information is hidden from the accounting.
What the theorem does and does not give
The theorem controls the population error of a consistent reconstructed hypothesis. It does not require the target to belong to a finite class, and it does not count the cardinality of the set of all possible classifiers. It does require independent examples, a fixed reconstruction rule, bounded retained size and side information, and consistency on the sample. A compression procedure can be statistically informative but computationally infeasible to find or reconstruct; runtime requires a separate analysis.
For noisy or nonrealizable data, a fully consistent reconstruction may not exist. One cannot simply delete the consistency assumption and retain the same proof: the unretained observations no longer all agree with the reconstructed hypothesis. Bounds that permit training errors use different tail estimates and must account for how those errors are selected.
Common mistake
(Forgetting that side bits multiply the count)
Suppose the threshold scheme is analyzed as though it needed no side information. For , and this gives , below the correct value . The side string selects among the three cases (mixed, all zero, all one), and the union bound must run over all strings, which here contributes . Whatever the reconstruction rule reads beyond the retained examples counts toward .
Common mistake
(Treating the retained examples as an ordinary training set)
Writing "train on the retained points and test on the other " suggests an ordinary train and test split. The retained points are chosen after looking at all examples, so the remaining are not an independent test set for the actually chosen subset. Independence holds only conditionally on a fixed index set, which is why the proof pays for every possible one.
Practice with solutions
Quick check
(For and , how many index subsets are possible if zero or one example may be retained? What changes in the union bound when side bits are also allowed?)
Count subsets of sizes 0 and 1, then count side strings.
Solution · Answer
There are subsets. Three bits permit side strings, so the union count is multiplied by eight.
Quick check
(A mixed labeled threshold sample has largest negative point and smallest positive point . Give a reconstructed threshold and explain why no sample point is misclassified.)
Use the midpoint rule.
Solution · Answer
Choose . By the definitions of the largest negative and smallest positive, every negative is at or below and every positive is at or above , so labels all sample points correctly.
Quick check
(A procedure claims , , but its reconstruction reads the full sample. Which step of the theorem's proof fails?)
Ask what is fixed once the retained examples and bits are fixed.
Solution · Answer
Conditioning on zero retained examples does not fix a classifier independent of the remaining observations: it is still computed from them. The probability for a fixed hypothesis therefore cannot be applied.
Quick check
(For fixed and confidence , explain why the displayed bound tends to zero as . No exact asymptotic constant is required.)
Bound the index sum by a power of .
Solution · Answer
The index sum is at most for , so its logarithm grows at most logarithmically in , while the denominator grows linearly. The ratio tends to zero.