Union Bounds in Learning Theory

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.

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.

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.

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 − δ'.

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.

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.

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 δ'.