2. Empirical Risk and Generalization

Previous: prediction and consistency · Next: linear classifiers and SVMs

Source: Lectures 9-13, pp. 31-46.

Part 1 estimated conditional probabilities and then classified. We now choose a predictor with small observed loss. The difficulty is that we select the predictor using the same sample on which we measure its error.

1. Why unrestricted training-error minimization fails

Under 0-1 loss,

$$R_n(f)=\frac{1}{n}\sum _{i}1\{f(X_i)\ne Y_i\},R(f)=\mathrm{Pr}(f(X)\ne Y).$$

Although Bayes minimizes $R$, minimizing $R_n$ over all functions can overfit.

Suppose ${\rho }_X$ has a density. Surround the distinct training inputs by disjoint balls whose union $B$ has probability at most $\epsilon$. Define

$$f_n(x)=\{\begin{array}{ll}{Y}_i,& x\text{ lies in the ball around }{X}_i,\\ 1-f_B(x),& x\notin B.\end{array}$$

Every label is memorized, so $R_n(f_n)=0$. Outside $B$, the conditional error is $\max \{\eta (x),1-\eta (x)\}\ge 1/2$. Thus

$$R(f_n)\ge \frac{1}{2}{\rho }_X(B^c)\ge \frac{1-\epsilon }{2}\ge \frac{1}{2}-\epsilon .$$

This is a counterexample, not an implementable algorithm: using the unknown Bayes rule shows that low training error alone does not identify a good predictor.

2. Restrict to a hypothesis class

Choose a fixed class $\mathcal{F}$, such as affine half-space classifiers. Distinguish

$${\hat{f}}_n\in \arg \underset{f\in \mathcal{F}}{\min }{R}_n(f),f_{\mathcal{F}}^{\ast }\in \arg \underset{f\in \mathcal{F}}{\min }R(f),f_B\in \arg \underset{f}{\min }R(f).$$

These are the best training fit, best population fit within the class, and unrestricted optimum. We write minimizers when they exist; infima and approximate minimizers give analogous bounds with an optimization-error term.

We want to compare $R({\hat{f}}_n)$ with its training error, with $R(f_{\mathcal{F}}^{\ast })$, and with Bayes risk $R^{\ast }$.

Uniform convergence

Define

$${\Delta }_n=\underset{f\in \mathcal{F}}{\sup }|R_n(f)-R(f)|.$$

First, $R({\hat{f}}_n)-R_n({\hat{f}}_n)\le {\Delta }_n$. For the second comparison, add and subtract empirical risks:

$$\begin{array}{rl}R({\hat{f}}_n)-R(f_{\mathcal{F}}^{\ast })& =[R({\hat{f}}_n)-R_n({\hat{f}}_n)]\\ & +[R_n({\hat{f}}_n)-R_n(f_{\mathcal{F}}^{\ast })]\\ & +[R_n(f_{\mathcal{F}}^{\ast })-R(f_{\mathcal{F}}^{\ast })]\\ & \le {\Delta }_n+0+{\Delta }_n=2{\Delta }_n.\end{array}$$

The middle term is nonpositive because ${\hat{f}}_n$ minimizes training risk.

A bound for one fixed $f$ is insufficient: choosing ${\hat{f}}_n$ after seeing the data changes the independence argument. A bound uniform over a predetermined class covers the selected predictor too.

Approximation error remains

$$\begin{array}{rl}R({\hat{f}}_n)-R^{\ast }& =[R({\hat{f}}_n)-R(f_{\mathcal{F}}^{\ast })]+[R(f_{\mathcal{F}}^{\ast })-R^{\ast }]\\ & \le 2{\Delta }_n+\underset{\mathrm{Approx}(\mathcal{F})}{\underbrace{\underset{f\in \mathcal{F}}{\inf }R(f)-R^{\ast }}}.\end{array}$$

The first term controls estimation error. The second measures how well the class represents an optimal rule. A richer class can reduce approximation error while making estimation harder.

Clarification of the lecture’s consistency statements: uniform convergence implies consistency relative to the best predictor in $\mathcal{F}$. Bayes consistency additionally requires approximation error to vanish. Necessity statements in VC learning theory involve distribution-free quantifiers; a pointwise claim for one distribution is not the full equivalence.

3. Finite classes: Hoeffding and a union bound

For fixed $f$, the losses are independent and bounded in $[0,1]$, so

$$\mathrm{Pr}(|R_n(f)-R(f)|\ge t)\le 2e^{-2n{t}^2}.$$

If $\mathcal{F}=\{f_1,\dots ,f_M\}$, a union bound gives

$$\mathrm{Pr}({\Delta }_n\ge t)\le \sum _{j=1}^M\mathrm{Pr}(|R_n(f_j)-R(f_j)|\ge t)\le 2M{e}^{-2n{t}^2}.$$

Set $2M{e}^{-2n{t}^2}=\delta$ and solve:

$$t=\sqrt{\frac{\log (2M/\delta )}{2n}}.$$

With probability at least $1-\delta$, this bounds ${\Delta }_n$, and twice this quantity bounds the ERM excess risk within the class.

For infinite classes, cardinality is too crude: different functions can behave identically on a finite sample.

4. Shattering and the growth function

Lectures 10-11; pp. 36-39.

For inputs $x_1,\dots ,x_n$, define

$${\mathcal{F}}_{x_1,\dots ,x_n}=\{(f(x_1),\dots ,f(x_n)):f\in \mathcal{F}\}.$$

The growth function, or shattering number, is

$$S(n,\mathcal{F})=\underset{x_1,\dots ,x_n}{\sup }|{\mathcal{F}}_{x_1,\dots ,x_n}|\le 2^n.$$

A set is shattered when every binary labeling can be realized. The supremum ranges over arrangements; one unshatterable arrangement does not establish a bound on $S$.

Affine classifiers in the plane

• One point admits both labels: $S(1)=2$.
• Two distinct points admit all four labelings: $S(2)=4$.
• Three collinear points cannot realize $(1,0,1)$ in their linear order. Three noncollinear points can realize all eight labelings, so $S(3)=8$.
• Four points cannot be shattered. Alternating labels on a convex quadrilateral cannot be separated by a line. If one point lies in the convex hull of the others, it cannot be separated from all the others. Degenerate arrangements also fail.

Thus affine half-spaces in ${\mathbb{R}}^2$ have VC dimension 3.

Deriving the VC probability bound

The lecture states, for $t\ge \sqrt{2/n}$,

$$\mathrm{Pr}({\Delta }_n\ge t)\le 4S(2n,\mathcal{F})e^{-n{t}^2/8}.$$

The following steps explain the independent-copy argument behind it.

1. Introduce a ghost sample. Let $D_n^{\prime }$ be independent, with empirical risk $R_n^{\prime }$. For a function selected using $D_n$, its ghost risk has conditional variance at most $1/(4n)$. Chebyshev gives

$$\mathrm{Pr}(|R_n^{\prime }(f)-R(f)|>t/2\mid D_n)\le \frac{1}{n{t}^2}\le \frac{1}{2}.$$

If a training sample exhibits deviation at least $t$, with probability at least $1/2$ the ghost risk is within $t/2$ of population risk. The two empirical risks then differ by at least $t/2$. With the usual measurability and supremum-approximation details,

$$\mathrm{Pr}({\Delta }_n\ge t)\le 2\mathrm{Pr}\left(\underset{f}{\sup }|R_n(f)-R_n^{\prime }(f)|\ge t/2\right).$$

2. Randomly swap paired observations. Swapping $(X_i,Y_i)$ with $(X_i^{\prime },Y_i^{\prime })$ independently leaves the joint distribution unchanged. Conditional on the pooled observations, the difference becomes

$$\frac{1}{n}\sum _i{\sigma }_i{d}_i(f),d_i(f)=\ell (f(X_i),Y_i)-\ell (f(X_i^{\prime }),Y_i^{\prime })\in [-1,1],$$

where ${\sigma }_i$ are independent random signs. Each summand has range width at most 2. Hoeffding bounds the probability of deviation $t/2$ for one labeling by $2e^{-n{t}^2/8}$.

3. Count behaviors. At most $S(2n,\mathcal{F})$ label vectors occur on the pooled inputs. A union bound contributes this factor; Step 1 contributes another factor 2. This gives the displayed VC inequality.

Solving for failure probability $\delta$ yields

$${\Delta }_n\le \sqrt{\frac{8}{n}\log \frac{4S(2n,\mathcal{F})}{\delta }}$$

with probability at least $1-\delta$. Exponential growth of $S(2n)$ need not give a shrinking bound, so we next control that growth.

5. VC dimension controls growth

Define

$$v=\mathrm{VC}(\mathcal{F})=\sup \{m:S(m,\mathcal{F})=2^m\}.$$

The Sauer-Shelah lemma, stated in the PDF, gives

$$S(n,\mathcal{F})\le \sum _{j=0}^{\min (v,n)}\left(\genfrac{}{}{0ex}{}{n}{j}\right).$$

For $1\le v\le n$, this is at most $(en/v{)}^v$. The restriction $v\le n$ matters; this expression is not a bound for arbitrary smaller $n$.

Substitute $S(2n)\le (2en/v{)}^v$ into the probability bound:

$${\Delta }_n\le \sqrt{\frac{8}{n}\left[v\log \frac{2en}{v}+\log \frac{4}{\delta }\right]}(1\le v\le 2n).$$

For fixed finite $v$, $\log n/n\to 0$ makes the bound vanish. Taking ${\delta }_n=n^{-2}$ makes failure probabilities summable; Borel-Cantelli then gives almost-sure uniform convergence.

Examples and empirical distribution functions

Affine half-spaces in ${\mathbb{R}}^d$ have VC dimension $d+1$. Thresholds $f_t(x)=1\{x\le t\}$ have VC dimension 1: one point is shattered, but two ordered points cannot receive labels $(0,1)$.

Applied to threshold averages, uniform convergence says

$$\underset{t}{\sup }\left|\frac{1}{n}\sum _{i}1\{X_i\le t\}-F_X(t)\right|\to 0\text{almost surely}.$$

This is the Glivenko-Cantelli property. To express it literally as a classification risk, take the constant label $Y=0$, so the threshold indicator equals its loss.

VC dimension measures worst-case input arrangements. Rademacher complexity uses the observed inputs or their distribution.

6. Rademacher complexity

Lectures 11-13; pp. 39-46.

Switch to labels and classifiers in $\{-1,1\}$. Independently of the sample, draw ${\sigma }_i$ with equally likely values $-1$ and $1$. Define

$${\hat{\mathfrak{R}}}_n(\mathcal{F})={\mathbb{E}}_{\sigma }\left[\underset{f\in \mathcal{F}}{\sup }\frac{1}{n}\sum _i{\sigma }_{i}f(X_i)\right],{\mathfrak{R}}_n(\mathcal{F})={\mathbb{E}}_X{\hat{\mathfrak{R}}}_n(\mathcal{F}).$$

Empirical complexity measures how well the class can align with random labels on the observed inputs.

For a singleton $\{f_0\}$, linearity and $\mathbb{E}{\sigma }_i=0$ give complexity 0. If the class shatters the distinct sample inputs, choose $f(X_i)={\sigma }_i$ to get

$$\underset{f}{\sup }\frac{1}{n}\sum _i{\sigma }_{i}f(X_i)=\frac{1}{n}\sum _i{\sigma }_i^2=1.$$

No correlation exceeds 1, so empirical complexity is exactly 1 in this case. Repeated inputs cannot always fit contradictory random labels.

Step 1: symmetrization with a ghost sample

To handle absolute values correctly, define two signed suprema:

$$G_{+}=\underset{f}{\sup }(R(f)-R_n(f)),G_{-}=\underset{f}{\sup }(R_n(f)-R(f)).$$

Then ${\Delta }_n=\max \{G_{+},G_{-}\}$. Since $R(f)={\mathbb{E}}_{D_n^{\prime }}{R}_n^{\prime }(f)$, moving the supremum outside the ghost expectation gives

$$\mathbb{E}{G}_{+}\le {\mathbb{E}}_{D_n,D_n^{\prime }}\underset{f}{\sup }[R_n^{\prime }(f)-R_n(f)].$$

For our label convention,

$$1\{f(X)\ne Y\}=\frac{1-Yf(X)}{2}.$$

Consequently,

$$R_n^{\prime }(f)-R_n(f)=\frac{1}{2n}\sum _i[Y_{i}f(X_i)-Y_i^{\prime }f(X_i^{\prime })].$$

Step 2: introduce random signs

Swapping each observation with its ghost partner independently leaves the joint law unchanged. Therefore

$$\begin{array}{rl}\mathbb{E}{G}_{+}& \le \frac{1}{2}\mathbb{E}\underset{f}{\sup }\frac{1}{n}\sum _i{\sigma }_i[Y_{i}f(X_i)-Y_i^{\prime }f(X_i^{\prime })]\\ & \le \frac{1}{2}\mathbb{E}\underset{f}{\sup }\frac{1}{n}\sum _i{\sigma }_i{Y}_{i}f(X_i)\\ & +\frac{1}{2}\mathbb{E}\underset{f}{\sup }\frac{1}{n}\sum _i(-{\sigma }_i)Y_i^{\prime }f(X_i^{\prime }).\end{array}$$

The last inequality uses ${\sup }_f(A_f+B_f)\le {\sup }_f{A}_f+{\sup }_f{B}_f$.

Step 3: absorb the labels

Conditional on all inputs and labels, multiplying an independent symmetric sign by a fixed $Y_i\in \{-1,1\}$ leaves it symmetric. The signs remain independent. Both expectations above thus equal ${\mathfrak{R}}_n$, giving

$$\mathbb{E}{G}_{+}\le {\mathfrak{R}}_n(\mathcal{F}).$$

Reversing the two samples proves $\mathbb{E}{G}_{-}\le {\mathfrak{R}}_n(\mathcal{F})$.

Correction to pp. 43-46: symmetry of the signs alone does not allow removal of an absolute value inside a supremum. A singleton has signed complexity zero but need not have zero expected absolute random correlation. The two signed-supremum argument avoids that step.

Step 4: concentration around expectation

Replacing one training observation changes $R_n(f)$ by at most $1/n$ for every $f$. Since

$$|\underset{f}{\sup }{a}_f-\underset{f}{\sup }{b}_f|\le \underset{f}{\sup }|a_f-b_f|,$$

each $G_{\pm }$ has bounded differences $c_i=1/n$. McDiarmid gives

$$\mathrm{Pr}(G_{\pm }-\mathbb{E}{G}_{\pm }\ge t)\le e^{-2n{t}^2}.$$

Union-bound the two events and take $t=\sqrt{\log (2/\delta )/(2n)}$. With probability at least $1-\delta$,

$${\Delta }_n\le {\mathfrak{R}}_n(\mathcal{F})+\sqrt{\frac{\log (2/\delta )}{2n}}.$$

These constants follow from the stated $\{-1,1\}$ convention; the PDF displays looser constants.

Step 5: use empirical complexity

Replacing one input changes a random correlation by at most $2/n$. Taking suprema and sign expectations preserves this bound, so ${\hat{\mathfrak{R}}}_n$ has bounded differences $2/n$. Its lower-tail bound is

$$\mathrm{Pr}({\mathfrak{R}}_n-{\hat{\mathfrak{R}}}_n\ge 2t)\le e^{-2n{t}^2}.$$

Combine this with the two events from Step 4. Set $t=\sqrt{\log (3/\delta )/(2n)}$ so the total failure probability is at most $\delta$. Then

$${\Delta }_n\le {\hat{\mathfrak{R}}}_n(\mathcal{F})+3\sqrt{\frac{\log (3/\delta )}{2n}}.$$

The extra term pays for estimating distribution-dependent complexity using the observed inputs.

7. Estimation in practice and the conclusion

For the fixed inputs:

1. Draw $B$ independent random-label vectors ${\sigma }^{(1)},\dots ,{\sigma }^{(B)}$.
2. Solve $m_b={\sup }_f{n}^{-1}{\sum }_i{\sigma }_i^{(b)}f(X_i)$ for each vector.
3. Approximate empirical complexity by $B^{-1}{\sum }_b{m}_b$.

This is ERM with random labels because

$$\frac{1}{n}\sum _{i}1\{f(X_i)\ne {\sigma }_i\}=\frac{1}{2}-\frac{1}{2n}\sum _i{\sigma }_{i}f(X_i).$$

Generating labels is cheap; optimizing can be expensive. A heuristic optimizer can underestimate the supremum, so it does not by itself provide a certified complexity upper bound.

If ${\mathfrak{R}}_n\to 0$ for a given distribution, summable failure probabilities imply ${\Delta }_n\to 0$ almost surely. ERM reaches the best risk within $\mathcal{F}$. For a universal statement, the condition must hold for every distribution. For Bayes consistency, approximation error must also vanish.

Local methods estimate $\eta$ and use consistency arguments; ERM methods control uniform deviations through class complexity. We now choose concrete classes and objectives: continue to Part 3.