Learning Theory

Keywords

learning theory, empirical risk minimization, Hoeffding’s inequality, union bound, uniform convergence, VC dimension

Lecture video: Discussion Section: Learning Theory · 1:26:03

Based on the Friday discussion section of CS229, Stanford University, Autumn 2018, taught by a member of the course staff.

Lecture 8 told you to choose models on held-out data because training error is optimistic. This section asks how optimistic, and answers with a theorem: if an algorithm picks the hypothesis with the lowest training error from a class of kk hypotheses, then with probability at least 1−δ1 - \delta its true error is within

212mlog⁡2kδ 2\sqrt{\frac{1}{2m}\log\frac{2k}{\delta}}

of the best the class can do. Two facts are hiding in that expression. The number of examples needed grows only with the logarithm of the size of the class, and, once the class is infinite, the logarithm is replaced by a measure of the class’s expressiveness called the VC dimension. Getting there takes two elementary tools — the union bound and Hoeffding’s inequality — and a change of viewpoint about what a learning algorithm is.

Ng explained in lecture 8 that this material used to be part of the main lectures and moved to a Friday section because it matters less to making algorithms work than it once did. The section promises to state results rather than prove them, and the proofs are in cs229-notes4. What this chapter adds is the section’s own pictures, its answers to questions, and a computation behind every claim: the bounds are checked against exact probabilities and simulations, which also shows how loose they are.

The learning algorithm as an estimator

1:15 Everything rests on two assumptions. There is a fixed data distribution D\mathcal D over pairs (x,y)(x, y), from which both the training set and every future test example are drawn; and the examples are drawn independently. Without the first, training data say nothing about test data, and the theory has nothing to work with. Lecture 8’s aside about training on phone recordings to deploy on a smart speaker is exactly a case where it fails.

3:15 A learning algorithm is then a box. In goes a training set S={(x(i),y(i))}i=1mS = \{(x^{(i)}, y^{(i)})\}_{i=1}^m of mm samples from D\mathcal D; out comes a hypothesis h^\hat h, or equivalently, for a parametric class such as logistic regression in nn dimensions, a parameter vector θ^\hat\theta. 4:43 The point the section makes first is that SS is random, the box is a deterministic function, and so its output is random too. Run the box on a different sample from D\mathcal D and you get a different θ^\hat\theta. In statistics the box is called an estimator, and the distribution of θ^\hat\theta over repeated draws of SS is its sampling distribution.

6:22 Against this randomness stands a fixed target, a true parameter θ∗\theta^* (or true hypothesis h∗h^*) that we would like the box to output. It is unknown, but it is not random: there is no distribution over it. That is the frequentist stance of lecture 8, and the notation follows it — hats for things estimated from data, stars for the true values we never see. Asked whether θ\theta must be a vector, the section answers that it can be anything we estimate, a scalar, a matrix, or a function with no parameters at all.

Bias and variance as moments of the sampling distribution

10:26 Lecture 8 pictured bias and variance in the data view: curves through points, underfitting and overfitting. The section redraws them in the parameter view, which makes them precise. Take a model with two parameters, so that each θ^\hat\theta is a dot in the plane. Draw a training set of size mm, run the algorithm, plot the dot; draw another training set of the same size, plot another dot; repeat. The cloud of dots is a sample from the sampling distribution. 13:51 Bias asks whether the cloud is centred on θ∗\theta^*: it is E[θ^]−θ∗\mathbb E[\hat\theta] - \theta^*, a statement about the first moment. Variance asks how spread out the cloud is, the second moment. They are, in the section’s words, “just properties of the first and second moments of your sampling distribution”.

Figure 1 draws the clouds for two real estimators on one regression problem, y=θ∗⊤x+εy = \theta^{*\top} x + \varepsilon with θ∗=(1,0.5)\theta^* = (1, 0.5) and two features correlated at 0.90.9 — the situation of square footage and number of bedrooms. Least squares is unbiased, and at m=10m = 10 its cloud is centred on θ∗\theta^* but enormous (total variance 1.471.47), stretched along the direction in which correlated features cannot be told apart: raising θ1\theta_1 while lowering θ2\theta_2 barely changes the fit. Ridge regression with λ=10\lambda = 10 on the same training sets is pulled towards the origin, a bias of length 0.520.52, and its variance is thirty times smaller, 0.0450.045. That is lecture 8’s claim that regularisation trades a little bias for a lot of variance, seen directly.

Figure 1: Sampling distributions of θ̂ for least squares (teal) and ridge with λ = 10 (indigo), 300 training sets per panel, on a two-feature regression with correlated features. The cross marks θ, the ring the mean of θ̂. More data shrinks both clouds, and shrinks ridge’s offset from θ too.

15:58 With ten times the data, every cloud tightens: least squares’ variance falls from 1.471.47 to 0.1100.110, roughly the factor of ten one expects from variance proportional to 1/m1/m. As m→∞m \to \infty the variance goes to zero, and an estimator whose output converges to θ∗\theta^* is called consistent. 17:56 An estimator with E[θ^]=θ∗\mathbb E[\hat\theta] = \theta^* at every mm is called unbiased.

17:14 The rate at which variance falls with mm the section calls statistical efficiency, a measure of how well an algorithm squeezes information from data, and it offers as examples one algorithm whose variance falls like 1/m21/m^2 and another like e−me^{-m}. Those rates are not available to an unbiased estimator of a parameter in a regular model: the Cramér–Rao bound puts a floor of order 1/m1/m under its variance. (Irregular models are different — the right endpoint of a uniform distribution can be estimated with variance of order 1/m21/m^2 — but the models in this course are regular.) What efficiency usually measures is the constant in front of 1/m1/m. The mean and the median of a Gaussian sample are both unbiased estimates of its centre, both with variance proportional to 1/m1/m; but the median’s is larger by a factor of π/2\pi/2. The generator measures m⋅Var⁡m \cdot \operatorname{Var} at 1.011.01 for the mean and 1.5751.575 for the median at m=101m = 101, against π/2=1.571\pi/2 = 1.571. Using the median wastes about a third of the data.

20:08 Informally, the section says, a high-bias algorithm is one that “no matter how much data or evidence you provide”, stays away from θ∗\theta^*. That runs two ideas together, and the bottom row of Figure 1 separates them. Bias is defined at a fixed mm, as a student’s question prompts the section to confirm at 21:35; staying away forever is inconsistency. Ridge with a fixed λ\lambda is biased at every mm and yet consistent, because the penalty stays the same size while the data term grows in proportion to mm: its bias is 0.520.52 at m=10m = 10, 0.180.18 at 100100, 0.0300.030 at 1,0001{,}000 and 0.0020.002 at 10,00010{,}000. 58:09 The same point answers a later question that the section leaves open, whether adding regularisation destroys the consistency of maximum likelihood. With a fixed penalty, it does not.

20:58 Bias and variance are separate properties; any combination of the two can occur. 22:18 High variance has two standard remedies. More data shrinks the cloud directly. Regularisation shrinks it by restricting where θ^\hat\theta can go, usually at the price of moving its centre — which is the trade Figure 1 shows.

Approximation error and estimation error

25:02 The second picture is drawn in the space of all hypotheses. Somewhere in it is gg, the best possible hypothesis, with the lowest expected error under D\mathcal D of any function whatsoever. 25:52 Our algorithm searches only a class H\mathcal H — all logistic regression models, say, or all SVMs — drawn as a region that need not contain gg. 26:27 Inside the region is h∗h^*, the best hypothesis in the class. And what training on finite data actually produces is h^\hat h, a different point of H\mathcal H for every training set.

27:51 For classification the error of a hypothesis is its probability of a mistake, and the training error is its frequency of mistakes on SS:

ε(h)=P(x,y)∼D(h(x)≠y),ε^S(h)=1m∑i=1m1{h(x(i))≠y(i)}.(1) \varepsilon(h) = P_{(x,y)\sim\mathcal D}\bigl(h(x) \neq y\bigr), \qquad \hat\varepsilon_S(h) = \frac1m \sum_{i=1}^m 1\bigl\{h(x^{(i)}) \neq y^{(i)}\bigr\}. \tag{1}

The first is called the generalisation error or risk; the second the empirical risk. 30:30 ε(g)\varepsilon(g) is the Bayes error, also called irreducible error: if the same xx can come with different labels, no function gets all of them right. Then the error of what we learn splits into three:

ε(h^)=ε(g)⏟Bayes error+ε(h∗)−ε(g)⏟approximation error+ε(h^)−ε(h∗)⏟estimation error.(2) \varepsilon(\hat h) = \underbrace{\varepsilon(g)}_{\text{Bayes error}} + \underbrace{\varepsilon(h^*) - \varepsilon(g)}_{\text{approximation error}} + \underbrace{\varepsilon(\hat h) - \varepsilon(h^*)}_{\text{estimation error}} . \tag{2}

31:35 The identity is a telescoping sum, but each term names a different cause. Approximation error is the price of restricting ourselves to H\mathcal H, a property of the class alone. 32:20 Estimation error is the price of having only mm examples, plus any quirks of the algorithm, and it shrinks as mm grows.

34:49 The section then says this decomposition and the bias–variance decomposition are related but not the same: estimation error itself splits into a variance part and a bias part, and “bias” in the usual sense is approximation error plus that estimation bias. For 0–1 loss this is a picture rather than an equation — there is no clean additive bias–variance identity for classification error — but for squared error it is exact, and worth seeing. Let g(x)=E[y∣x]g(x) = \mathbb E[y \mid x], let hˉ=ES[h^]\bar h = \mathbb E_S[\hat h] be the average learned hypothesis, and measure error by ε(h)=E(y−h(x))2\varepsilon(h) = \mathbb E(y - h(x))^2. Then

ES ε(h^)=σ2⏟noise+Ex(hˉ(x)−g(x))2⏟bias2+ES,x(h^(x)−hˉ(x))2⏟variance,(3) \mathbb E_S\,\varepsilon(\hat h) = \underbrace{\sigma^2}_{\text{noise}} + \underbrace{\mathbb E_x\bigl(\bar h(x) - g(x)\bigr)^2}_{\text{bias}^2} + \underbrace{\mathbb E_{S,x}\bigl(\hat h(x) - \bar h(x)\bigr)^2}_{\text{variance}} , \tag{3}

and when H\mathcal H is a linear space, such as all straight lines, g−h∗g - h^* is orthogonal to it, so Pythagoras splits the bias: bias2=approximation error+Ex(hˉ−h∗)2\text{bias}^2 = \text{approximation error} + \mathbb E_x(\bar h - h^*)^2, and the estimation error is the variance plus that same small term.

Figure 2 does this for straight lines fitted to eight points from a parabola, g(x)=4(x−12)2g(x) = 4(x - \frac12)^2, with noise σ=0.3\sigma = 0.3. The best line is flat, h∗=13h^* = \frac13, and the approximation error is 0.08890.0889. The expected test error of the fitted line is 0.25970.2597, which splits as 0.0900+0.0889+0.08080.0900 + 0.0889 + 0.0808 one way and 0.0900+0.0910+0.07860.0900 + 0.0910 + 0.0786 the other. The difference between the two middle terms, 0.00210.0021, is the estimation bias: the average fitted line, 0.290−0.006x0.290 - 0.006x, is not h∗h^*, because least squares on a misspecified model is biased at small mm. The generator asserts that both totals agree and that the Pythagorean identity holds.

Figure 2: Left: the hypothesis-space picture. The class H is a region; the best predictor g lies outside it; h* is the point of H closest to g; fitted hypotheses ĥ scatter inside H. Right: the expected test error of straight lines fitted to eight noisy points from a parabola, split into Bayes, approximation and estimation error, and into noise, squared bias and variance. The bars are to scale and their totals agree.

36:34 The picture also says how to fight each kind of error. To reduce bias, make H\mathcal H bigger, so that it reaches closer to gg; but a bigger class gives h^\hat h more room to wander, so variance tends to rise. 39:27 To reduce variance, make H\mathcal H smaller — regularisation does this, by penalising hypotheses with large θ\theta — and unless the shrinking happens to move towards gg, bias rises. 41:05 A student asks why not shrink the class towards h∗h^*; because we do not know where h∗h^* is, and if we did there would be nothing to learn.

Empirical risk minimisation and two tools

44:56 Nothing so far depended on what happens inside the box. To prove something, the section now fixes the algorithm: empirical risk minimisation returns the hypothesis with the lowest training error,

h^=arg⁡min⁡h∈Hε^S(h).(4) \hat h = \arg\min_{h \in \mathcal H} \hat\varepsilon_S(h). \tag{4}

47:36 This is “what we’ve been doing so far in the course”, with one honest caveat that the section mentions: logistic regression minimises the logistic loss, not the 0–1 training error of Equation 1, and SVMs minimise the hinge loss. Those losses are convex stand-ins for the count of mistakes, which is intractable to minimise directly. The theorems below are about the count of mistakes; they extend to the stand-ins with more work, which this section does not do.

49:25 Two questions organise the rest. How close is the training error of a hypothesis to its true error? And how close is the true error of the hypothesis ERM picks to that of the best in the class? 50:47 The first tool is the union bound: for any events A1,…,AkA_1, \dots, A_k, independent or not,

P(A1∪⋯∪Ak)≤P(A1)+⋯+P(Ak). P(A_1 \cup \dots \cup A_k) \le P(A_1) + \dots + P(A_k).

“If this looks trivial, it is trivial,” the section says. 52:00 The second is Hoeffding’s inequality, stated for the case needed here. Let Z1,…,ZmZ_1, \dots, Z_m be independent Bernoulli(ϕ\phi) variables and ϕ^=1m∑iZi\hat\phi = \frac1m\sum_i Z_i their mean. Then for any γ>0\gamma > 0,

P(∣ϕ^−ϕ∣>γ)≤2exp⁡(−2γ2m).(5) P\bigl(|\hat\phi - \phi| > \gamma\bigr) \le 2\exp(-2\gamma^2 m). \tag{5}

The probability that an average of coin flips misses its expectation by more than a margin γ\gamma falls exponentially in the number of flips. The general version holds for any bounded independent variables, and the bound on the range is essential.

The bound is easy to check, because the exact probability is a binomial tail. Figure 3 compares them for γ=0.1\gamma = 0.1. At m=100m = 100 the exact probabilities are 0.0350.035 for a fair coin and 0.00340.0034 for ϕ=0.15\phi = 0.15, against a bound of 0.270.27. The bound holds at every mm and ϕ\phi the generator tries, with the exact tail never more than 0.230.23 of it. It has the right exponential rate, and it is loosest for coins far from fair, whose averages vary less — a looseness that matters here, because error rates of good classifiers are far from one half.

Figure 3: The probability that the mean of m coin flips misses φ by more than 0.1: computed exactly for φ = 0.5 and φ = 0.15, and bounded by Hoeffding’s inequality. The bound is valid everywhere and loose by an order of magnitude or more. The φ = 0.15 curve leaves the plot below 10⁻⁶.

Uniform convergence for a finite class

59:54 The section’s central picture puts every hypothesis in H\mathcal H on a horizontal axis and plots two curves above it: the true error ε(h)\varepsilon(h), a fixed curve, and the training error ε^S(h)\hat\varepsilon_S(h), a random curve that changes with every training set. Figure 4 computes it for a class small enough that the true error of every member is a closed form. Inputs are uniform on [0,1][0,1], the label is 1{x≥0.4}1\{x \ge 0.4\} flipped with probability 0.150.15, and H\mathcal H contains ten threshold classifiers ht(x)=1{x≥t}h_t(x) = 1\{x \ge t\} with t=0.05,0.15,…,0.95t = 0.05, 0.15, \dots, 0.95. The Bayes error is 0.150.15. The class has no threshold at 0.40.4, so its best members, t=0.35t = 0.35 and t=0.45t = 0.45, have error 0.1850.185, an approximation error of 0.0350.035.

Figure 4: True error ε(h) (solid) and training error on three samples of sixty examples (dashed) for each of ten threshold classifiers. The training-error curves scatter around the true curve. ERM on the first sample picks the hypothesis circled, whose training error is well below its true error: choosing the minimum selects a hypothesis whose training error happened to come out low.

1:05:19 For one hypothesis hh fixed in advance, the training error is an average of mm independent Bernoulli variables 1{h(x(i))≠y(i)}1\{h(x^{(i)}) \ne y^{(i)}\} whose mean is ε(h)\varepsilon(h), so Hoeffding applies directly:

P(∣ε^S(h)−ε(h)∣>γ)≤2exp⁡(−2γ2m). P\bigl(|\hat\varepsilon_S(h) - \varepsilon(h)| > \gamma\bigr) \le 2\exp(-2\gamma^2 m).

On average over training sets the dashed curve passes through the solid one at every hh, and with more data it hugs it more tightly. 1:08:16 But this is useless as it stands, and the section is precise about why: ERM does not fix hh in advance. It looks at the training set and picks the hypothesis whose dashed curve is lowest, so h^\hat h depends on SS and its training error is no longer an unbiased average. It is the minimum of noisy scores, which lecture 8 showed is optimistic. The circled point in Figure 4 is exactly that.

1:09:32 The fix is to demand that the whole dashed curve be close to the solid one at once — uniform convergence. If no hypothesis deviates by more than γ\gamma, then neither does the one ERM picks, however it was chosen. 1:11:54 For a class of kk hypotheses the union bound gives this cheaply: the event that some hh deviates is the union of kk events, each of probability at most 2exp⁡(−2γ2m)2\exp(-2\gamma^2 m), so

P(∃ h∈H:∣ε^S(h)−ε(h)∣>γ)≤2kexp⁡(−2γ2m).(6) P\bigl(\exists\, h \in \mathcal H : |\hat\varepsilon_S(h) - \varepsilon(h)| > \gamma\bigr) \le 2k\exp(-2\gamma^2 m). \tag{6}

Equivalently, with probability at least 1−δ1 - \delta, where δ=2kexp⁡(−2γ2m)\delta = 2k \exp(-2\gamma^2 m), every hypothesis has training error within γ\gamma of its true error.

The union bound is pessimistic, since it treats the kk events as if they could not overlap, and nested thresholds overlap heavily. With m=200m = 200 and γ=0.1\gamma = 0.1 the generator finds that some hypothesis among the ten deviates in 1.6 %1.6\,\% of training sets. The bound for a single hypothesis is already 3.7 %3.7\,\%, and the union bound is 37 %37\,\%. The guarantees in learning theory are worst-case statements over every distribution, and they read best as statements about how quantities scale.

1:16:04 Three quantities are tied together — mm, γ\gamma and δ\delta — and fixing any two gives the third. Fixing γ\gamma and δ\delta and solving for mm gives the sample complexity: with probability at least 1−δ1 - \delta, every training error is within γ\gamma of the true error, provided

m≥12γ2log⁡2kδ.(7) m \ge \frac{1}{2\gamma^2}\log\frac{2k}{\delta}. \tag{7}

The striking feature is the logarithm. For γ=δ=0.05\gamma = \delta = 0.05, ten hypotheses need 1,1991{,}199 examples, a thousand need 2,1202{,}120, and a million need only 3,5013{,}501.

How good is the hypothesis ERM picks?

1:17:58 The second question compares h^\hat h with the best in class. On the event that uniform convergence holds, a three-step chain does it, each step either uniform convergence or the definition of ERM:

ε(h^)≤ε^S(h^)+γ≤ε^S(h∗)+γ≤ε(h∗)+2γ. \varepsilon(\hat h) \le \hat\varepsilon_S(\hat h) + \gamma \le \hat\varepsilon_S(h^*) + \gamma \le \varepsilon(h^*) + 2\gamma .

The first step drops from the solid curve to the dashed one at h^\hat h. The second uses the fact that h^\hat h has the lowest training error of any hypothesis, h∗h^* included. The third climbs from the dashed curve back to the solid one at h∗h^*. 1:22:29 Substituting γ\gamma from Equation 6 gives the theorem: with probability at least 1−δ1 - \delta,

ε(h^)≤(min⁡h∈Hε(h))+212mlog⁡2kδ.(8) \varepsilon(\hat h) \le \Bigl(\min_{h \in \mathcal H} \varepsilon(h)\Bigr) + 2\sqrt{\frac{1}{2m}\log\frac{2k}{\delta}} . \tag{8}

This is bias and variance once more, in theorem form. The first term is the best the class can do, which can only fall as H\mathcal H grows; the second, which grows with kk, is the price of searching a larger class with the same data. cs229-notes4 makes the same reading. On the threshold class the guarantee holds in every one of 3,000 runs at each mm the generator tries, but it is very loose: at m=200m = 200 and δ=0.05\delta = 0.05, 2γ2\gamma is 0.2450.245, while ERM picks a best-in-class threshold in every run.

Infinite classes and the VC dimension

1:23:40 Most classes of interest, linear classifiers among them, are infinite, and Equation 8 with k=∞k = \infty says nothing. The section ran out of time here and only stated the result; cs229-notes4, section 4, gives more, and two pieces of it are worth having.

The first is a crude argument that gets the right answer. A class with dd real parameters, stored as 64-bit floating-point numbers, has at most k=264dk = 2^{64d} members, and log⁡k=64dlog⁡2\log k = 64 d \log 2 is linear in dd. So the sample complexity of ERM over a dd-parameter class grows linearly in dd. With γ=δ=0.05\gamma = \delta = 0.05 the bound gives about 9,6009{,}600 examples for d=1d = 1 and 89,00089{,}000 for d=10d = 10, which is far too many in absolute terms and right in how it scales.

The second is the principled version. A class H\mathcal H shatters a set of points if, for every one of the 2n2^n ways of labelling them, some h∈Hh \in \mathcal H gets every label right. The Vapnik–Chervonenkis dimension VC(H)\mathrm{VC}(\mathcal H) is the size of the largest set H\mathcal H can shatter. For lines in the plane it is 3, and Figure 5 shows why: three points in general position can be split by a line under all eight labellings, while no four points can. Any four points in general position either form a convex quadrilateral, where the labelling that alternates around it defeats every line, or a triangle with a point inside, where labelling the inner point against the outer three does. The generator checks every labelling of each set by exhaustive search over line directions. The definition needs only one shattered set of size 3: three collinear points cannot be shattered, since no line puts the middle point on the other side from its two neighbours, and the VC dimension is still 3.

Figure 5: Shattering with lines. Left: three points in general position under all eight labellings, each separated by a line (the all-same labellings need none). Right: the two shapes four points in general position can take, each with a labelling no line separates. The VC dimension of lines in the plane is therefore 3.

1:24:52 Vapnik’s theorem then replaces log⁡k\log k with the VC dimension dd: with probability at least 1−δ1 - \delta,

ε(h^)≤ε(h∗)+O(dmlog⁡md+1mlog⁡1δ), \varepsilon(\hat h) \le \varepsilon(h^*) + O\Bigl(\sqrt{\frac{d}{m}\log\frac{m}{d} + \frac1m\log\frac1\delta}\Bigr),

and the section’s take-away is that the number of examples needed is of the order of the VC dimension. For most classes with a reasonable parametrisation the VC dimension is roughly the number of parameters — linear classifiers in nn dimensions have n+1n + 1 — which is the formal version of Ng’s rule of thumb in lecture 8 that unregularised models want at least as many examples as parameters.

The VC dimension also answers the question from lecture 8 about why an SVM in an infinite-dimensional feature space does not overfit. The VC dimension of all linear separators in that space is infinite. But Ng’s answer was that the relevant class is the separators with a large margin, and for data inside a ball of radius RR the VC dimension of separators with margin at least γ\gamma is bounded in terms of R2/γ2R^2/\gamma^2, however many dimensions the feature space has. That is the sense in which minimising ∥w∥2\lVert w \rVert^2 is regularisation.

NoteIn the official notes

cs229-notes4, sections 2 and 3, prove the finite-class results stated here, including the sample-complexity corollary; section 4 gives the 64-bit argument, the definition of shattering and Vapnik’s theorem. Hoeffding’s inequality is proved in the supplementary notes on Hoeffding’s inequality, via Chernoff bounds and moment generating functions.