4
$\begingroup$

I have a function class $\mathcal{F}$. I get $n$ samples according to a model $$y = f^*(x)+\epsilon$$

I find the best $\hat{f}$ from these training samples i.e. $$\hat{f} = \arg\min\limits_{f\in \mathcal{F}} \frac{1}{n}\sum\limits_{i=1}^n (y_i-f(x_i))^2$$

Let $\bar{f} = E[\hat{f}]$, where the expectation is over all training samples.

Now, the average testing error is given by \begin{align*} E[(y_0-\hat{f}(x_0))^2] &= E\left[\left((y_0-f^*(x_0)) + (f^*(x_0)-\bar{f}(x_0)) + (\bar{f}(x_0)-\hat{f}(x_0))\right)^2\right]\\ &= E[(y_0-f^*(x_0))^2] + \color{red}{E\left[\left((f^*(x_0)-\bar{f}(x_0)) + (\bar{f}(x_0)-\hat{f}(x_0))\right)^2\right]}\\ &\stackrel{\color{red}{?}} = E[(y_0-f^*(x_0))^2] + \color{red}{E\left[(f^*(x_0)-\bar{f}(x_0))^2\right] + E\left[(\bar{f}(x_0)-\hat{f}(x_0))^2\right]} \end{align*} The second step is because $y_0-f^*(x_0)=\epsilon_0$, which is independent of $x_0$. However, I don't see how $f^*(x_0)-\bar{f}(x_0)$ is independent of $\bar{f}(x_0)-\hat{f}(x_0)$ for the third step.

$f^*(x_0)-\bar{f}(x_0)$ relates to the average over all samples while $\bar{f}(x_0)-\hat{f}(x_0)$ depends on the current sample, and we know the samples are independent, but how does that imply their independence?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

I believe the cause of your puzzlement is the confounding of the expectations between the training and test sets. This is unfortunately not made explicit in many textbooks.

Note that the term $E[(y_0-\hat{f}(x_0))^2]$ is over both training and test sets (I am using test set as a stand-in for the true data distribution). The expectation needs to be written as $E_{T, S}[(y_0-\hat{f}(x_0))^2]$, where $T$ is the training set and $S$ is the test set.

\begin{align*} E_{T, S}[(y_0-\hat{f}(x_0))^2] &= E_S[E_{(T|S)}((y_0-\hat{f}(x_0))^2)]\\ &=E_S[E_{T}((y_0-\hat{f}(x_0))^2)]\\ &=E_S\left[E_{T}\left[\left((y_0-f^*(x_0)) + (f^*(x_0)-\bar{f}(x_0)) + (\bar{f}(x_0)-\hat{f}(x_0))\right)^2\right]\right]\\ \end{align*}

  1. The first equality is by rewriting the joint expectation in terms of the conditional expectation.
  2. The second equality is due to the independence of the training and test sets.

Now in the expectation

\begin{align*} E_{T}\left[\left((y_0-f^*(x_0)) + (f^*(x_0)-\bar{f}(x_0)) + (\bar{f}(x_0)-\hat{f}(x_0))\right)^2\right] \end{align*}

the first two summands are constants because they don't depend on the training set. Now we can use the fact that for a constant $a$ and r.v. $X$, $E[(a+X)^2] = a^2 + E[X^2]$ if $E[X] = 0$. Therefore

\begin{align*} E_{T, S}[(y_0-\hat{f}(x_0))^2] &= \\ &=E_S\left[\left((y_0-f^*(x_0)) + (f^*(x_0)-\bar{f}(x_0)\right)^2 + E_{T}\left[(\bar{f}(x_0)-\hat{f}(x_0)^2\right]\right] \\ \end{align*}

Now you should be able to derive the final expression that you want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.