Machine Learning from First Principles

Chapter 11 · Part II: Supervised Learning

Learning Theory

How many examples are enough to trust a training error? Why do flexible models need more data? Learning theory answers with inequalities, and the two tools needed to prove them fit on one page.

After this chapter you will be able to

  • State precisely what it means for a learning algorithm to generalize.
  • Use the union bound and Hoeffding’s inequality, and apply them to a held-out test set.
  • Derive uniform-convergence and sample-complexity bounds for finite hypothesis classes.
  • Define shattering and the VC dimension, and state the VC generalization bound.
  • Explain PAC learning and structural risk minimization.
  • Explain what classical theory does and does not explain about deep networks.

Earlier chapters gave practical answers to the question “will this model work on new data?”: hold out a test set, cross-validate, watch the gap between training and validation error. Learning theory gives mathematical answers. Under the i.i.d. assumption of Section 1.3, how many examples are enough to trust the training error? Why do more flexible model classes need more data? How large can the gap between training and test error be? The answers are inequalities, and the two tools needed to prove them fit on one page.

11.1The Question Learning Theory Asks

Fix a hypothesis class $\mathcal H$ (all linear classifiers, all trees of depth 3, …) and a binary classification problem with examples $(\vx,y)$ drawn i.i.d. from a distribution $\mathcal D$. For a hypothesis $h\in\mathcal H$ define

$$\begin{aligned}\text{generalization (true) error:}\quad & \varepsilon(h)=\Prob_{(\vx,y)\sim\mathcal D}\big[h(\vx)\ne y\big], \\ \text{training (empirical) error:}\quad & \hat\varepsilon(h)=\frac1n\sum_{i=1}^n\mathbb 1\big[h(\vx^{(i)})\ne y^{(i)}\big].\end{aligned}$$

Empirical risk minimization (ERM) returns $\hat h=\argmin_{h\in\mathcal H}\hat\varepsilon(h)$. Let $h^*=\argmin_{h\in\mathcal H}\varepsilon(h)$ be the best hypothesis in the class. We would like to show that $\varepsilon(\hat h)$ is close to $\varepsilon(h^*)$: that the hypothesis we picked using the training data is nearly as good as the best one we could have picked had we known $\mathcal D$.

11.2Two Tools: The Union Bound and Hoeffding’s Inequality

Lemma 11.1 (Union bound)

For any events $A_1,\dots,A_k$, $\Prob(A_1\cup\dots\cup A_k)\le\Prob(A_1)+\dots+\Prob(A_k)$.

Theorem 11.2 (Hoeffding’s inequality)

Let $Z_1,\dots,Z_n$ be independent random variables taking values in $[0,1]$ with common mean $\phi$, and let $\hat\phi=\frac1n\sum_iZ_i$. For any $\gamma>0$,

$$\Prob\big(|\hat\phi-\phi|>\gamma\big)\le2\exp(-2\gamma^2n) \tag{11.1}$$

Hoeffding’s inequality is a quantitative law of large numbers: the probability that an average misses its mean by more than $\gamma$ decays exponentially in the sample size. Unlike the central limit theorem it holds exactly for every $n$, not just in a limit, at the price of a somewhat loose constant.

Example: How big must a test set be?

For a fixed classifier, each test example contributes $Z_i=\mathbb 1[h(\vx_i)\ne y_i]\in\{0,1\}$, so the test error $\hat\phi$ estimates the true error $\phi$. To be within $\gamma=0.01$ with probability at least $1-\delta=0.95$, set $2e^{-2\gamma^2n}\le\delta$:

$$n\ge\frac{\log(2/\delta)}{2\gamma^2}=\frac{\log 40}{2\times10^{-4}}\approx18{,}400 .$$

With 1,000 test examples, the guaranteed accuracy is only $\gamma=\sqrt{\log40/2000}\approx0.043$: a reported 92% could truly be anywhere from about 88% to 96%. This is why benchmark differences of a fraction of a percentage point on small test sets deserve suspicion. Crucially, the bound holds only for a classifier chosen before looking at the test set (Chapter 1).

11.3Finite Hypothesis Classes

Suppose $\mathcal H=\{h_1,\dots,h_k\}$ is finite. For a single fixed $h_j$, Hoeffding gives $\Prob(|\hat\varepsilon(h_j)-\varepsilon(h_j)|>\gamma)\le2e^{-2\gamma^2n}$. But ERM does not use a fixed hypothesis; it picks the one that looks best on the training data, and the one that looks best is likely to be one whose training error happens to be too optimistic. The fix is to demand that all hypotheses are estimated accurately at once. By the union bound,

$$\Prob\big(\exists\,h\in\mathcal H:\ |\hat\varepsilon(h)-\varepsilon(h)|>\gamma\big)\le\sum_{j=1}^k2e^{-2\gamma^2n}=2k\,e^{-2\gamma^2n}.$$

Equivalently, with probability at least $1-\delta$ (where $\delta=2ke^{-2\gamma^2n}$), every hypothesis satisfies $|\hat\varepsilon(h)-\varepsilon(h)|\le\gamma$. This is called uniform convergence. Solving for $n$ and $\gamma$ gives two useful forms.

Sample complexity. Uniform convergence to within $\gamma$ holds with probability $1-\delta$ as soon as

$$n\ \ge\ \frac{1}{2\gamma^2}\log\frac{2k}{\delta}. \tag{11.2}$$

The required number of examples grows only logarithmically in the number of hypotheses.

Error bound for ERM. If uniform convergence holds, then

$$\varepsilon(\hat h)\le\hat\varepsilon(\hat h)+\gamma\le\hat\varepsilon(h^*)+\gamma\le\varepsilon(h^*)+2\gamma,$$

where the middle step uses that $\hat h$ minimizes the training error. Therefore, with probability at least $1-\delta$,

$$\varepsilon(\hat h)\ \le\ \underbrace{\min_{h\in\mathcal H}\varepsilon(h)}_{\text{approximation}}+\underbrace{2\sqrt{\frac{1}{2n}\log\frac{2k}{\delta}}}_{\text{estimation}} \tag{11.3}$$

Key idea: Bias and variance, rigorously

Equation (11.3) is a precise version of the bias–variance trade-off of Section 5.2. Enlarging $\mathcal H$ can only lower the first term (a bigger class contains better hypotheses: less bias) but raises the second through $\log k$ (more ways to fit noise: more variance). More data shrinks only the second term.

A finite class may sound restrictive, but every model stored on a computer is finite: $d$ parameters stored as 64-bit numbers allow $k=2^{64d}$ hypotheses, so $\log k=64d\log2$, and the sample complexity grows linearly in the number of parameters. The next section reaches the same conclusion more elegantly.

11.4Infinite Hypothesis Classes and the VC Dimension

Definition 11.1 (Shattering and VC dimension)

A class $\mathcal H$ shatters a set of points $\{\vx_1,\dots,\vx_m\}$ if, for every one of the $2^m$ possible labelings, some $h\in\mathcal H$ classifies all the points correctly. The Vapnik–Chervonenkis (VC) dimension $\mathrm{VC}(\mathcal H)$ is the size of the largest set that $\mathcal H$ can shatter.

Example: Lines in the plane

Linear classifiers $h(\vx)=\mathbb 1[\vw\T\vx+b\ge0]$ in $\R^2$ can shatter three points that are not collinear: every one of the 8 labelings can be produced by some line. No set of four points can be shattered: for four points in convex position, the labeling that alternates around the quadrilateral (the XOR pattern of Chapter 15) cannot be separated, and if one point lies inside the triangle of the other three, labeling it differently from the three is impossible. So the VC dimension is 3. In general, halfspaces in $\R^d$ have VC dimension $d+1$, the number of parameters.

The VC dimension measures the effective capacity of a class. The central result of the theory (Vapnik 1998) replaces $\log k$ by the VC dimension:

Theorem 11.3 (VC bound)

Let $D=\mathrm{VC}(\mathcal H)$. With probability at least $1-\delta$, for all $h\in\mathcal H$,

$$|\varepsilon(h)-\hat\varepsilon(h)|\ \le\ O\!\left(\sqrt{\frac{D}{n}\log\frac nD+\frac1n\log\frac1\delta}\right), \tag{11.4}$$

and consequently $\varepsilon(\hat h)\le\varepsilon(h^*)+O\big(\sqrt{(D/n)\log(n/D)+(1/n)\log(1/\delta)}\big)$.

The number of examples needed to learn well is therefore roughly proportional to the VC dimension: for most model families, roughly linear in the number of parameters. The proof uses a “ghost sample” argument to reduce an infinite class to the finitely many labelings it can produce on $2n$ points (at most about $(2n)^D$ of them, by Sauer’s lemma), then applies the finite-class argument.

Margins beat dimension. The VC dimension of linear classifiers grows with $d$, yet SVMs work with millions of features or infinite-dimensional kernels (Chapter 9). The explanation is that linear classifiers achieving margin at least $\gamma$ on data inside a ball of radius $R$ have VC dimension at most about $R^2/\gamma^2$, independent of $d$. Large margins mean low effective capacity, which is the theoretical justification for maximizing the margin.

11.5PAC Learning

The framework above is called probably approximately correct (PAC) learning (Valiant 1984): with probability at least $1-\delta$ (“probably”), the learned hypothesis has error at most $\varepsilon$ (“approximately correct”). A class is PAC-learnable if this can be achieved for every $\varepsilon,\delta$ with a number of samples polynomial in $1/\varepsilon$ and $1/\delta$.

In the realizable case, where some $h\in\mathcal H$ has zero error, the rate improves. A fixed hypothesis with true error above $\varepsilon$ makes zero training errors with probability at most $(1-\varepsilon)^n\le e^{-\varepsilon n}$, so by the union bound, ERM returns a hypothesis with error at most $\varepsilon$ with probability $1-\delta$ once

$$n\ge\frac1\varepsilon\Big(\log k+\log\frac1\delta\Big), \tag{11.5}$$

a rate of $1/\varepsilon$ instead of $1/\varepsilon^2$.

11.6Model Selection Through the Lens of Theory

Structural risk minimization. Arrange model classes in a nested sequence $\mathcal H_1\subset\mathcal H_2\subset\cdots$ (polynomials of increasing degree, say). Rather than minimizing training error over the largest class, minimize training error plus the complexity term of the bound for each class, and choose the class with the smallest total. This is the theoretical counterpart of regularization: penalties such as $\lambda\norm\vw^2$ restrict the effective class to small-norm weight vectors, whose capacity is smaller.

Why validation works. Choosing among $k$ trained models by their validation error is ERM over a finite class of size $k$, evaluated on fresh data. By Equation (11.3), the chosen model is within $2\sqrt{\log(2k/\delta)/(2n_{\text{val}})}$ of the best of the $k$, which explains both why validation is reliable and why trying very many configurations (large $k$) on a small validation set leads to the optimistic bias of Chapter 12.

11.7What Classical Theory Misses

Apply the VC bound to a modern network with 25 million parameters trained on 1.3 million images: the complexity term exceeds 1, so the bound says nothing (an error rate can never exceed 1 anyway). Worse, such networks can fit randomly shuffled labels perfectly (Zhang et al. 2017), so any bound that depends only on the class must be vacuous for them: the same class contains both the network that generalizes and the one that memorizes noise. Yet the networks trained on real labels generalize well.

The resolution pursued in current research is that what matters is not the capacity of the whole class but which hypothesis the training procedure actually finds. Candidate explanations include implicit regularization by gradient descent (Section 5.6), norm- and margin-based bounds that depend on the size of the learned weights rather than their number, PAC-Bayesian bounds that reward solutions robust to weight perturbations (flat minima), and the structure of real data, which lies near low-dimensional manifolds (Section 8.2). Some of these give nonvacuous bounds for real networks, but a complete theory of deep-learning generalization does not yet exist. The classical results remain the right mental model for what can go wrong: too little data for too flexible a procedure, and too many choices made on the same held-out set.

11.8Summary

  • Learning theory bounds the gap between training error $\hat\varepsilon(h)$ and true error $\varepsilon(h)$ under the i.i.d. assumption.
  • Hoeffding: an average of $n$ bounded independent variables misses its mean by more than $\gamma$ with probability at most $2e^{-2\gamma^2n}$; this sizes test sets.
  • With the union bound, uniform convergence over $k$ hypotheses needs $n\ge\frac{1}{2\gamma^2}\log\frac{2k}{\delta}$, and ERM is then within $2\gamma$ of the best hypothesis in the class.
  • The VC dimension (largest shattered set; $d+1$ for halfspaces in $\R^d$) replaces $\log k$ for infinite classes; margin bounds make SVMs dimension-free.
  • PAC learning formalizes “probably approximately correct”; structural risk minimization and validation are model selection with complexity control.
  • Class-based bounds are vacuous for deep networks; explaining their generalization is an open research problem.

11.9Exercises

  1. MathUsing Hoeffding’s inequality, how many test examples guarantee that an estimated error is within $0.02$ of the true error with probability $0.99$?
  2. MathFill in the three inequalities that lead from uniform convergence to Equation (11.3), explaining which assumption each uses.
  3. MathShow that the class of intervals on the real line, $h(x)=\mathbb 1[a\le x\le b]$, has VC dimension 2.
  4. MathShow that three collinear points cannot be shattered by lines in $\R^2$, but some set of three points can. Why does the definition of VC dimension only require some set to be shattered?
  5. MathDerive the realizable-case sample complexity $n\ge\frac1\varepsilon(\log k+\log\frac1\delta)$ from $(1-\varepsilon)^n\le e^{-\varepsilon n}$ and the union bound.
  6. CodingSimulate ERM over $k$ threshold classifiers $h_t(x)=\mathbb 1[x\ge t]$ on noisy one-dimensional data. For $n=20,50,200,1000$, plot the average gap $\varepsilon(\hat h)-\hat\varepsilon(\hat h)$ over 500 repetitions, and compare with the bound $\sqrt{\log(2k/\delta)/(2n)}$.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.