Union Bounds in Learning Theory

One Hypothesis, Few Defining Examples

A learning rule A can receive a training sequence S containing m examples but return a hypothesis that is determined by only k of those examples. Theorem 30.2 studies this situation by separating the examples that determine the hypothesis from the examples that were not selected for that purpose. The proof then accounts for every relevant way those k examples might be chosen.

Tracing the Selected and Unselected Parts

Start with the full training sequence S. A choice of k positions identifies the examples used to determine a hypothesis. The examples not selected for that purpose are collected in V. This separation is central to the theorem: the selected examples define the hypothesis, while V contains the remaining examples used in the theorem's stated condition.

Enumerating Every Index Choice

The proof does not assume one fixed choice of k examples at the beginning. Instead, for every index choice I in [m]^k, it defines h_I = B(z_i1, ..., z_ik). Thus, each possible index choice considered by the proof has an associated hypothesis. This enumeration is necessary because the examples that determine the returned hypothesis may correspond to different positions in the training sequence.

The number of possible choices enters the proof through the combinatorial factor (m choose k). The proof's bookkeeping therefore has two layers: define a hypothesis for each possible index choice, then control the relevant probability statements across all those choices.

Combining Failure Events

For an individual index choice, the proof has a probability statement involving δ. Because there are multiple possible index choices, a statement for only one choice is not enough. The proof applies the union bound to combine the statements for all choices considered. This changes the probability parameter from δ to δ' and produces a probability statement of at least 1 − δ'.

δ' = (m choose k) × δ

A Numerical Probability Calculation

This example illustrates only the bookkeeping performed by the proof. The calculation accounts for the number of possible choices and the individual parameter δ; it does not add a separate performance conclusion.

Why m Must Reach 2k

The theorem's probability-bound derivation requires m ≥ 2k. At the level of the sample split, this means that after k examples are selected, the remaining count m − k is at least k. The condition therefore supports the derivation by ensuring the selected and unselected portions have the required size relationship for the probability argument used in the proof.

Mistakes to Avoid

• Treating the returned hypothesis as if it must use all m examples.

  Theorem 30.2 specifically studies the case where the returned hypothesis is determined by only k of the m examples.

  Fix: Separate the k determining examples from the remaining examples.

• Confusing V with the selected examples.

  V consists of the unselected examples, while the selected examples are used in h_I = B(z_i1, ..., z_ik).

  Fix: Use V for the examples left after the determining k examples have been identified.

• Analyzing only one index choice.

  The proof defines h_I for possible index choices and must account for all relevant choices.

  Fix: Track the combinatorial factor (m choose k) and apply the union bound.

• Using δ instead of δ' after the union-bound step.

  The proof changes the parameter because it accounts for the selection factor.

  Fix: Calculate δ' = (m choose k) × δ, then use the resulting 1 − δ' statement.

• Treating m ≥ 2k as the formula for δ'.

  m ≥ 2k is a requirement supporting the probability-bound derivation, not the union-bound parameter calculation.

  Fix: Check m ≥ 2k separately, then calculate δ' from (m choose k) × δ.

Practice the Proof Bookkeeping

The Proof in One Pass

1. Begin with a training sequence S containing m examples.
2. Identify a possible choice I of k example indices.
3. Use the selected examples to define h_I = B(z_i1, ..., z_ik).
4. Collect the unselected examples in V.
5. Repeat the construction conceptually for the possible index choices considered by the proof.
6. Apply the union bound across those choices.
7. Replace δ with δ' = (m choose k) × δ, obtaining a probability statement of at least 1 − δ'.
8. Use the requirement m ≥ 2k as part of the probability-bound derivation.

The central structure is selection plus accounting. The hypothesis is determined by k examples, the rest are placed in V, and the proof avoids committing to only one possible selection. The union bound accounts for the possible index choices, which is why the probability parameter changes from δ to δ'.