Compression-Based Generalization Bounds

A Smaller Description Inside a Larger Sample

A learning rule A can receive a training sequence S containing m examples, yet return a hypothesis whose contents are determined by only k of those examples. Compression-based generalization bounds study what can be concluded from this smaller determining subset. The proof tracks both the examples that determine the hypothesis and the examples that were not selected.

From A to the Compressed Hypothesis

Theorem 30.2 describes a learning rule A that receives the full sequence S of m examples. The returned hypothesis is determined by k examples through a mapping B. If the selected examples have indices i1 through ik, the proof writes the associated hypothesis as h_I = B(z_i1, ..., z_ik). Thus, A may inspect the full training sequence, while the hypothesis it returns is determined by the selected examples represented through B.

The Unselected Set V

Once k examples are selected, the remaining examples are collected in the set V. V is not merely leftover notation: it is central to the theorem's stated condition. The proof separates the examples used to determine h_I from the examples that were not selected, allowing the probability argument to be expressed in terms of the compressed part and its complement.

Why Every Index Choice Matters

The proof does not assume one fixed choice of k examples from the beginning. For every index choice I in [m]^k, it defines h_I = B(z_i1, ..., z_ik). Each possible choice therefore creates a corresponding hypothesis and a corresponding event that must be controlled. The union bound then combines the probability statements for these separate choices.

The Adjusted Probability Parameter

δ' = (m choose k) × δ

The Role of m ≥ 2k

The proof requires m ≥ 2k. Under this requirement, the number of unselected examples, m-k, is at least as large as the number of selected examples, k. This relationship supports the probability-bound derivation used in the theorem. It is therefore a condition on the sizes of the two parts of the training sequence, not a claim that the hypothesis uses all m examples.

Mistakes in Reading the Proof

• Assuming that A uses only k examples as input.

  Theorem 30.2 describes A as receiving a sequence S containing m examples. The returned hypothesis is determined by k of them.

  Fix: Keep the full input S and the k-example determining subset conceptually distinct.

• Ignoring V after selecting the k examples.

  The unselected examples form V, which is central to the theorem's stated condition.

  Fix: Explicitly identify V as the collection of the remaining m-k examples.

• Applying the probability statement to only one index choice.

  The proof defines h_I for possible index choices and combines the corresponding probability statements with a union bound.

  Fix: Account for the selection factor (m choose k) when forming δ'.

• Confusing δ with δ'.

  The proof introduces δ' = (m choose k) × δ.

  Fix: Calculate δ' from the number of possible k-index choices and δ.

• Treating m ≥ 2k as an optional numerical detail.

  The requirement supports the probability-bound derivation by ensuring that m-k is at least k.

  Fix: Check the size condition before applying the proof structure.

Check Your Understanding

Proof Structure at a Glance

1. A receives a training sequence S of m examples, while the returned hypothesis is determined by k examples through B.
2. The selected examples determine h_I, and the unselected examples form V.
3. The proof considers possible index choices rather than assuming one fixed subset.
4. A union bound combines the probability statements for those choices, introducing δ' = (m choose k) × δ.
5. The condition m ≥ 2k ensures that the unselected portion has size m-k at least as large as k, supporting the probability-bound derivation.