Homework 3

Stat 154/254: Statistical Machine Learning

1 Infinitely fine step function ULLN fail

In this homework problem, we carefully work through an example of poor generalization in a specific problem.

Let $x_n \overset{\mathrm{IID}}{\sim}\textrm{Unif}(0,1)$, $y\overset{\mathrm{IID}}{\sim}\mathcal{N}\left(0,1\right)$ independently of $x$, and $(x_n, y_n)$ be IID draws from a joint distribution. For each $K$, define the step functions

\[ z_{jK} = \mathrm{I}\left((j - 1)/K \le x\le j/K\right) \quad\textrm{for}\quad j=1,\ldots,K. \]

Define the function class

\[ \mathcal{F}= \left\{ f(x; \boldsymbol{\beta}) = \sum_{K=1}^\infty \sum_{j=1}^K \beta_{jK} z_{jK}(x) \textrm{ for some set of }\beta_{jK} \right\}. \]

Note that the vector $\boldsymbol{\beta}$ may be infinitely long. Finally, define

\[ \hat{\mathscr{R}}(f) := \frac{1}{N} \sum_{n=1}^N(f(x_n) - y_n)^2 \quad\textrm{and}\quad \mathscr{R}(f) = \mathbb{E}_{\vphantom{}}\left[(f(x) - y)^2\right] \]

(a)

Show that $\mathbb{E}_{\vphantom{}}\left[z_{jK}\right] = \mathbb{E}_{\vphantom{}}\left[z_{jK}^2\right] = 1/K$ and so

\[ \mathbb{E}_{\vphantom{}}\left[f(x; \boldsymbol{\beta})\right] = \sum_{K=1}^\infty \frac{1}{K} \sum_{j=1}^K \beta_{jK}. \]

(b)

Define $\mathcal{F}_K := \left\{ f(x; \boldsymbol{\gamma}) = \sum_{j=1}^K \gamma_{j} z_{jK}(x) \textrm{ for some set of }\gamma_{j} \right\}$. Show that $\mathcal{F}_K \subset \mathcal{F}$.

(c)

With probability one, all $x_n$ are distinct in any dataset of size $N$. Show that you can take $K$ large enough that there exists $f\in \mathcal{F}_K$ such that

\[ \begin{aligned} \hat{\mathscr{R}}(\hat{\boldsymbol{\gamma}}) ={}& \frac{1}{N} \sum_{n=1}^N(f(x_n, \hat{\boldsymbol{\gamma}}) - y_n)^2 ={} 0, \end{aligned} \]

where $\hat{\boldsymbol{\gamma}}$ is the OLS estimator of $\boldsymbol{\gamma}$.

(d)

Show that $\mathscr{R}(f) \ge 1$ for any $f$.

(e)

Combine the above results to show that $\mathcal{F}$ does not satisfy a ULLN in the sense that

\[ \sup_{f\in \mathcal{F}} \left|\hat{\mathscr{R}}(f) - \mathscr{R}(f)\right| \ge 1. \]

2 Low estimation error with poor generalization error

In this problem, we emphasize how low generalization error is sufficient but not necessary for low estimation error.

Recall our decomposition of estimation error,

\[ \underbrace{\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f})}_{\textrm{Estimation error}} ={} \underbrace{\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})}_{\textrm{"Generalization error"}} + \underbrace{\hat{\mathscr{R}}(\hat{f}) - \hat{\mathscr{R}}(\overline{f})}_{\textrm{$\le 0$}} + \underbrace{\hat{\mathscr{R}}(\overline{f}) - \mathscr{R}(\overline{f})}_{\textrm{LLN term}}. \]

Let us define a strange–looking estimator that has poor generalization error, but still provides low estimation error. For a fixed $\delta > 0$, define

\[ \hat{f}(\boldsymbol{x}; \delta) = \overline{f}(\boldsymbol{x}) + \sum_{n=1}^N\mathrm{I}\left(\left\Vert\boldsymbol{x}- \boldsymbol{x}_n\right\Vert \le \delta\right) (y_n - \overline{f}(\boldsymbol{x})). \]

Assume that $\hat{\mathscr{R}}(f) = 0$ if $f(\boldsymbol{x}_n) = y_n$ for every $n$ in the training set. That is, the empirical risk is zero if $f$ is able to interpolate the training data.

Assume that $\boldsymbol{x}$ has a continuous distribution, so that $p(\left\Vert\boldsymbol{x}- \boldsymbol{x}_0\right\Vert \le C) \rightarrow 0$ as $C \rightarrow 0$ for any $\boldsymbol{x}_0$.

(a) Show that there exists a $\delta > 0$ sufficiently small so that $\hat{\mathscr{R}}(\hat{f}(\cdot; \delta)) = 0$.

(b) Show that $\mathbb{E}_{\boldsymbol{x}}\left[\mathrm{I}\left(\left\Vert\boldsymbol{x}- \boldsymbol{x}_n\right\Vert \le \delta\right)\right] \rightarrow 0$ as $\delta \rightarrow 0$ for every $n$.

(c) Show that $\mathscr{R}(\hat{f}(\boldsymbol{x}; \delta)) \rightarrow \mathscr{R}(\overline{f})$ as $\delta \rightarrow 0$.

(d) As $\delta \rightarrow 0$, what happens to the generlization error, $\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})$?

(e) As $\delta \rightarrow 0$, what happens to the “negative term,” $\hat{\mathscr{R}}(\hat{f}) - \hat{\mathscr{R}}(\overline{f})$?

(f) As $\delta \rightarrow 0$, what happens to the estimation error, $\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f})$?

(g) Describe in your own words how it is that $\hat{f}(\cdot; \delta)$ fails to have low generalization error, and yet has low estimation error.

(h) Describe a sense in which $\hat{f}(\cdot; \delta)$ “overfits” the training data for small $\delta$, and a sense in which it does not.

3 Leave–one–out with an estimator that depends strongly on N

This example is designed to strengthen the intuition about why leave–K–out estimators are biased.

Consider $y_n \overset{\mathrm{IID}}{\sim}\mathcal{N}\left(5, 1\right)$ and squared loss: $\mathscr{L}(\hat{y}, y) = (\hat{y}- y)^2$, and $\mathscr{R}(f) = \mathbb{E}_{\vphantom{}}\left[(f- y)^2\right]$. We will have no regressors, so our estimating functions are just constants.

We will take $N = 100$ for this problem, and let $\boldsymbol{Y}_{-n}$ denote the leave–one–out vector, $\boldsymbol{Y}_{-n} = (y_1, \ldots, y_{n-1}, y_{n+1}, \ldots, y_N)$.

An estimation procedure $F$ takes in a dataset $\boldsymbol{Y}= (y_1, \ldots, y_N)$ and returns a constant estimate $\hat{y}= F(\boldsymbol{Y}) \in \mathbb{R}^{}$. For this, we consider the (silly) estimator

\[ \hat{y}= F(\boldsymbol{Y}) = \begin{cases} 5 & \textrm{if the length of }\boldsymbol{Y}\ge 100 \\ 0 & \textrm{if the length of }\boldsymbol{Y}< 100. \end{cases} \]

(a)

What is the optimal estimate, $f^{\star}= \underset{f}{\mathrm{argmin}}\, \mathscr{R}(f)$?

(b)

What is $\mathscr{R}(F(\boldsymbol{Y}))$? What is $\mathscr{R}(F(\boldsymbol{Y}_{-n}))$?

(c)

Recall the leave–one–out cross–validation (CV) estimator

\[ \hat{\mathscr{R}}_{CV}(\boldsymbol{Y}) := \frac{1}{N} \sum_{n=1}^N\mathscr{R}(F(\boldsymbol{Y}_{-n}, y_n)). \]

What is $\mathbb{E}_{\boldsymbol{Y}}\left[\hat{\mathscr{R}}_{CV}(\boldsymbol{Y})\right]$? Is the leave–one–out CV estimator an unbiased estimate of $\mathscr{R}(F(\boldsymbol{Y}))$?

(d)

Connect this toy example with the intuition that leave–$K$–out CV tends to be more biased for larger $K$.

4 Leave–one–out CV for linear regression

This homework problem derives a closed-form expression for the effect of leave–one–out CV for linear regression.

We will use the following result, known as the Woodbury formula (but also many other names, including the Sherman-Morrison-Woodbury formula). Let $A$ denote an invertible matrix, and $\boldsymbol{u}$ and $\boldsymbol{v}$ vectors the same length as $A$. Then

\[ (A + \boldsymbol{u}\boldsymbol{v}^\intercal)^{-1} ={} A^{-1} - \frac{A^{-1} \boldsymbol{u}\boldsymbol{v}^\intercal A^{-1}}{1 + \boldsymbol{v}^\intercal A^{-1} \boldsymbol{u}}. \]

We will also use the definition of a “leverage score” from lecture $h_n := \boldsymbol{x}_n^\intercal(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{x}_n$. Note that $h_n = (\boldsymbol{X}(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{X}^\intercal)_{nn}$ is the $n$–th diagonal entry of the projection matrix $\underset{\boldsymbol{X}}{\boldsymbol{P}}$.

Let $\hat{\boldsymbol{\beta}}_{-n}$ denote the estimate of $\hat{\beta}$ with the datapoint $n$ left out. Similarly, let $\boldsymbol{X}_{-n}$ denote the $\boldsymbol{X}$ matrix with row $n$ left out, and $\boldsymbol{Y}_{-n}$ denote the $\boldsymbol{Y}$ matrix with row $n$ left out.

(a)

Prove that

\[ \hat{\boldsymbol{\beta}}_{-n} = (\boldsymbol{X}_{-n}^\intercal\boldsymbol{X}_{-n})^{-1} \boldsymbol{X}_{-n}^\intercal\boldsymbol{Y}_{-n} = (\boldsymbol{X}^\intercal\boldsymbol{X}- \boldsymbol{x}_n \boldsymbol{x}_n^\intercal)^{-1} (\boldsymbol{X}^\intercal\boldsymbol{Y}- \boldsymbol{x}_n y_n) \]

(b)

Using the Woodbury formula, derive the following expression: \[ (\boldsymbol{X}^\intercal\boldsymbol{X}- \boldsymbol{x}_n \boldsymbol{x}_n^\intercal)^{-1} = (\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} + \frac{(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{x}_n \boldsymbol{x}_n^\intercal(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} }{1 - h_n} \]

(c)

Combine (a) and (b) to derive the following explicit expression for $\hat{\boldsymbol{\beta}}_{-n}$:

\[ \hat{\boldsymbol{\beta}}_{-n} = \hat{\boldsymbol{\beta}}- (\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{x}_n \frac{1}{1 - h_n} \hat{\varepsilon}_n. \]

(d)

Using (c), derive the following explicit expression the leave-one-out error on the $n$–th observation:

\[ y_n - \boldsymbol{x}_n^\intercal\hat{\boldsymbol{\beta}}_{-n} = \frac{\hat{\varepsilon}_n}{1 - h_n}. \]

(e)

Using (d), prove that the leave–one–out CV estimator of $\mathscr{R}(\hat{\boldsymbol{\beta}})$ is given by

\[ \frac{1}{N} \sum_{n=1}^N(y_n - \boldsymbol{x}_n^\intercal\hat{\boldsymbol{\beta}}_{-n})^2 = \frac{1}{N} \sum_{n=1}^N\frac{\hat{\varepsilon}_n^2}{(1 - h_n)^2}, \]

where $\hat{\varepsilon}_n = y_n - \hat{y}_n$ is the residual from the full regression without leaving any data out. Using this formula, leave–one–out CV can be computed using only the original regression and $(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1}$ rather than doing $N$ separate matrix inversions.

5 VC dimension of linear classifiers

Consider the class of $P$–dimensional linear binary classifiers, $\mathcal{F}= \{ \mathrm{I}\left(\boldsymbol{x}^\intercal\boldsymbol{\beta}\ge 0\right) \textrm{ for any }\boldsymbol{\beta}\in \mathbb{R}^{P}\}$. In this problem, we will show that the VC dimension of $\mathcal{F}$ is $P$. In doing so we then prove a generalization bound for logistic regression with zero–one loss.

For $N$ points, let $\boldsymbol{X}$ denote the $N \times P$ matrix with $\boldsymbol{x}_n^\intercal$ in row $n$. In this problem, the $\boldsymbol{x}_n$ are not given to us — we will be choosing them to find sets that can or cannot be shattered.

First, we show that we can shatter any set of size $P$ in (a)–(c), showing that the VC dimension is greater than or equal to $P$. Then, in (d)–(f) we show that we cannot shatter a set of size $P + 1$, and so the VC dimension is less than or equal to $P+1$. It follows that the VC dimension is $P$.

(a)

Suppose we are given $N$ points, $\boldsymbol{x}_1, \ldots, \boldsymbol{x}_N$. For any $y_1, \ldots, y_N$, define $z_n = 2 y_n - 1$. Show that $y_n$ is correctly classified if we can find $\hat{\boldsymbol{\beta}}$ such that $\hat{\boldsymbol{\beta}}^\intercal\boldsymbol{x}= z_n$.

(b)

When $N=P$, identify an $\boldsymbol{X}$ so that, for any $\boldsymbol{Z}\in \mathbb{R}^{P}$, you can find a $\hat{\boldsymbol{\beta}}$ such that $\boldsymbol{X}\hat{\boldsymbol{\beta}}= \boldsymbol{Z}$. Hint: There are actually an infinite number of $\boldsymbol{X}$ that will work, but also some that won’t.

(c)

Use (a) and the $\boldsymbol{X}$ you identified in (b) to conclude that there exists a set of size $P$ points, $\boldsymbol{x}_1, \ldots, \boldsymbol{x}_P$, that you can shatter with classifiers in $\mathcal{F}$.

(d)

Now, suppose that $N = P + 1$, and you are given $N$ points $\boldsymbol{x}_1, \ldots, \boldsymbol{x}_N$. Let the rank of $\boldsymbol{X}$ be $Q$, and note that $Q \le P$. Assume without loss of generality that the first $Q$ rows of $\boldsymbol{X}$ are linearly independent (if they’re not, just re-order the rows of $\boldsymbol{X}$). Show that you can find $\boldsymbol{\gamma}$ such that $\boldsymbol{x}_{Q+1} = \sum_{n=1}^Q \gamma_n \boldsymbol{x}_{n}$. That is, show that the $Q + 1$–th row is a linear combination of the first $Q$ rows.

(e)

Continuing (d), suppose we set $y_n = \mathrm{I}\left(\gamma_n > 0\right)$ for $n=1,\ldots,Q$, and suppose that $\hat{\boldsymbol{\beta}}$ correctly classifies these first $Q$ points. Using (d), show that $\hat{\boldsymbol{\beta}}^\intercal\boldsymbol{x}_{Q+1} \ge 0$.

(f)

Using (e), define a set of $P+1$ points that cannot be shattered.

(g)

Putting your results together, what is the VC dimension of $\mathcal{F}$?

6 VC dimension of zero–one loss

Suppose we have a function class $\mathcal{F}$ of classifiers that has VC dimension $P < \infty$. In this problem, we extend the ULLN results from class to zero–one loss. Let $\hat{f}\in \mathcal{F}$ be a classifier estimated from the observed data, $(\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_N, y_N)$.

(a)

Given that the VC dimension is finite, what can you conclude about $\left|\frac{1}{N} \sum_{n=1}^N\hat{f}(\boldsymbol{x}_n) - \mathbb{E}_{\vphantom{}}\left[\hat{f}(\boldsymbol{x})\right]\right|$ as $N \rightarrow \infty$?

Explain in intuitive terms what this expression means. (Note that $y_n$ occurs in this expression only through $\hat{f}$, so this expression is not estimating the classification error.)

(b)

Note that $\mathcal{F}$ is a class of functions on $\boldsymbol{x}$. Define a new function class $\mathcal{F}'$ consisting of functions defined on $(\boldsymbol{x}, y)$ as follows:

\[ \mathcal{F}' = \{ f'(\boldsymbol{x}, y) = \mathrm{I}\left( f(\boldsymbol{x}) \ne y\right) \textrm{ for } f\in \mathcal{F}\}. \]

Show carefully that if $\mathcal{F}$ is able to shatter a set of size $P$ of values $\{ \boldsymbol{x}_1, \ldots, \boldsymbol{x}_P \}$ then $\mathcal{F}'$ is able to shatter a set of size $P$ of values $\{ (\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_P, y_P) \}$.

(c)

In the setting of (b), show carefully that if $\mathcal{F}'$ is able to shatter a set of size $P$ of values $\{ (\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_P, y_P) \}$, then $\mathcal{F}$ is able to shatter a set of size $P$ of values $\{ \boldsymbol{x}_1, \ldots, \boldsymbol{x}_P \}$.

(d)

Using (b) and (c), what can you conclude about the VC dimension of $\mathcal{F}'$?

(e)

What can you conclude about the generalization error of linear classifiers with zero–one loss? Specifically, what happens to \[ \sup_{f \in \mathcal{F}} \left|\frac{1}{N} \sum_{n=1}^N\mathrm{I}\left(f(\boldsymbol{x}_n) \ne y_n\right) - \mathbb{P}_{\,}\left(f(\boldsymbol{x}) \ne y\right)\right| \]

as $N \rightarrow \infty$?

(f)

Let $\hat{\boldsymbol{\beta}}$ denote the estimate from logistic regression (which was trained with logistic loss, not the zero–one loss), and consider the binary classifier $f(\boldsymbol{x}; \boldsymbol{\beta}) = \mathrm{I}\left(\boldsymbol{x}^\intercal\boldsymbol{\beta}\ge 0\right)$. What can you conclude about

\[ \left|\frac{1}{N} \sum_{n=1}^N\mathrm{I}\left(f(\boldsymbol{x}; \hat{\boldsymbol{\beta}}) \ne y_n\right) - \mathbb{P}_{\,}\left(f(\boldsymbol{x}; \hat{\boldsymbol{\beta}}) \ne y\right)\right| \]

as $N \rightarrow \infty$?

7 Use the ULLN to prove logistic regression consistency (254 only $\star$ $\star$ $\star$)

Consider the logistic regression loss for binary $y$ and bounded regression coefficients:

\[ \mathcal{F}:= \{ f(\boldsymbol{x}; \boldsymbol{\beta}) = \exp(\boldsymbol{x}^\intercal\boldsymbol{\beta}) / (1 + \exp(\boldsymbol{x}^\intercal\boldsymbol{\beta})) \textrm{ such that }\left\Vert\boldsymbol{\beta}\right\Vert_2^2 \le K\} \]

\[ \mathscr{L}(f(\boldsymbol{x}; \boldsymbol{\beta}), y) := - y\boldsymbol{\beta}^\intercal\boldsymbol{x}+ \log(1 + \exp(\boldsymbol{\beta}^\intercal\boldsymbol{x})). \]

Assuming that $\mathbb{E}_{\vphantom{}}\left[\left\Vert\boldsymbol{x}\right\Vert\right] < \infty$, show that $\mathcal{F}$ satisfies the integrable Lipchitz condition and so has vanishing generalization error:

\[ \sup_{f\in \mathcal{F}} \left|\hat{\mathscr{R}}(f) - \mathscr{R}(f)\right| \rightarrow 0. \]

Hint: you can establish that a function is Lipschitz by bounding the derivative.