Generalization, Model Capacity, and Learning Guarantees

Definition A hypothesis class $\mathcal{H}$ is the set of predictors $h$ that a learning procedure is allowed to choose from. It is finite when it has finitely many members, and $\lvert \mathcal{H} \rvert$ denotes their number. The guarantees on this page assume the following setting. The examples $(\mathbf{X}_1, Y_1), \dots, (\mathbf{X}_n, Y_n)$ are independent draws from one distribution $P$, the population whose risk we want to describe. The loss satisfies $0 \le L(y, \hat{y}) \le 1$ for every possible target and prediction. The class is fixed before the sample is drawn, so it does not depend on these examples. For each $h$ in $\mathcal{H}$ the population risk and the empirical risk are

where $(\mathbf{X}, Y)$ is a new draw from $P$. The gap of $h$ is $\Delta_n(h) = \lvert \hat{R}_n(h) - R(h) \rvert$. Its value depends on the random sample.

Definition Let $Z_1, \dots, Z_n$ be independent random variables with $a \le Z_i \le b$ for every $i$, where $a < b$ are constants, and let $\bar{Z}$ be their average. Hoeffding’s inequality states that for every $\varepsilon > 0$

For one predictor $h$ fixed before the sample is drawn, the losses $Z_i = L(Y_i, h(\mathbf{X}_i))$ are independent, lie in $[0, 1]$ and have mean $R(h)$, so

The probability is over the random sample, and the factor 2 covers deviations in both directions. The inequality uses only independence and the range of the losses, so it holds for every distribution $P$. The same generality makes it loose for many particular distributions. It applies to a predictor fixed in advance. A predictor chosen because its empirical risk is small depends on the sample, and the inequality does not apply to it directly.

Definition The union bound states that for any events $A_1, \dots, A_k$

with no assumption of independence. A class $\mathcal{H}$ has the uniform convergence property for a loss when, for every $\varepsilon > 0$ and every $\delta$ in $(0, 1)$, there is a sample size $n_0$ such that for every $n \ge n_0$ and every distribution $P$, a sample of $n$ independent draws from $P$ gives $\sup_{h \in \mathcal{H}} \Delta_n(h) < \varepsilon$ with probability at least $1 - \delta$. In the setting above, apply the union bound to the events $\Delta_n(h) \ge \varepsilon$, one for each member, and bound each by Hoeffding’s inequality.

So every finite class with losses in $[0, 1]$ has the property, and any $n_0 \ge \ln(2\lvert \mathcal{H} \rvert/\delta)/(2\varepsilon^2)$ works.

Definition A generalization bound limits the population risk of a learned predictor by quantities computed from the training sample, with a stated probability over the draw of that sample. For a finite class the derivation above gives the following theorem. Suppose the class is fixed before the sample is drawn, the $n$ examples are independent draws from $P$, the loss takes values in $[0, 1]$ and $\delta$ is in $(0, 1)$. Setting $2\lvert \mathcal{H} \rvert e^{-2n\varepsilon^2} = \delta$ and solving gives

with the natural logarithm. Then, with probability at least $1 - \delta$, every $h$ in $\mathcal{H}$ satisfies $\Delta_n(h) \le \varepsilon$. Because this event covers every member, it covers a member $\hat{h}$ chosen with the same sample. If $\hat{h}$ minimizes the empirical risk over $\mathcal{H}$ and $h^*$ minimizes the population risk over $\mathcal{H}$, both of which exist because the class is finite, then on the same event

The first and last steps use the uniform event, and the middle step holds because $\hat{h}$ has the smallest empirical risk. The theorem says nothing about how good $h^*$ is, and it can be loose, since Hoeffding’s inequality ignores the actual spread of the losses and the union bound ignores overlap between members.

Definition Capacity describes how rich a hypothesis class is, how many different patterns of predictions its members can produce, and therefore how easily some member can match a sample by chance. No single measure applies to every class. In the finite-class bound the measure is $\ln \lvert \mathcal{H} \rvert$, the logarithm of the number of distinct predictors. The number of parameters is a different quantity. A class indexed by even one real-valued parameter usually contains infinitely many predictors, so the finite-class bound gives no conclusion about it, and infinite classes need other capacity measures, such as the VC dimension, each with its own theorem and assumptions. Two rules follow from the derivation. Replacing $\lvert \mathcal{H} \rvert$ by any number $M \ge \lvert \mathcal{H} \rvert$ keeps the bound valid, because $\varepsilon$ increases with the class size. And the class must contain every predictor the whole procedure could have returned, across every candidate model, hyperparameter setting and feature subset the data might have led to, all fixed before the sample is drawn. Counting only the candidates a search happened to try is not enough, and an adaptive search over networks with real-valued weights can reach infinitely many predictors.

Definition The inductive bias of a learning procedure is the set of assumptions or preferences, beyond the training data, that leads it to favor some predictors over others that fit the same data equally well. It enters through the class, such as linear functions, through penalties, such as the ridge preference for small weights, and through built-in structure, such as smoothness or the sharing of weights across positions in an image model. The no free lunch theorem shows that some bias is unavoidable. One version concerns a finite input set $\mathcal{X}$, labels in $\{0, 1\}$ and zero-one loss. If the target function $f$ is drawn uniformly from all $2^{\lvert \mathcal{X} \rvert}$ functions from $\mathcal{X}$ to $\{0, 1\}$, then for every learning algorithm whose internal randomness is independent of $f$, and any training inputs chosen independently of $f$ and labeled by $f$, the predicted label at any input outside the training inputs is correct with probability exactly $1/2$. Averaged over all targets, every algorithm therefore has the same error on unseen inputs, $1/2$, so an advantage on some targets is exactly offset on others. Another version, in the same binary setting, shows that for every algorithm and every training size below half the number of possible inputs, some distribution has a predictor with zero risk while the algorithm’s risk is at least $1/8$ with probability at least $1/7$ over the sample.