sample compression bounds

If a learner can throw away almost all of its training data and still reconstruct exactly the same hypothesis from a tiny surviving subset, then that hypothesis cannot be very complicated — it is, in effect, summarized by those few retained examples. Sample compression turns this into a generalization guarantee: the fewer examples you need to keep in order to rebuild your predictor, the better it will generalize. Compression is a witness to simplicity.

A compression scheme of size k maps any training set to a subset of at most k examples, the compression set, plus possibly a few side bits, such that a fixed reconstruction function applied to that subset reproduces the learner's hypothesis. Since there are at most order m to the k ways to choose the retained examples from m, a counting-plus-union-bound argument gives generalization error on the order of k log m plus log one over delta, all over m, for consistent schemes, and a square-root version in the agnostic case — entirely without reference to VC dimension or any hypothesis-class capacity. The support vectors of an SVM are the archetypal compression set.

Sample compression is a strikingly different route to generalization — combinatorial and algorithm-specific rather than class-based — and a deep result shows it is essentially equivalent in power to VC theory: every class of VC dimension d admits a compression scheme of size roughly d, resolving a long-standing question. It directly explains nearest-neighbor and SVM generalization and underlies set-based and dictionary methods. The caveat: the bounds require the reconstruction to depend only on the compression set, so they apply to a specific algorithmic structure rather than to arbitrary learners.