1
$\begingroup$

Consider $2N$ i.i.d random variables $x_1,\dots, x_{2N}$ drawn from an unknown distribution $X$. Let $f$ be a continuous function such that $f(X)$ has finite mean and variance. For $1\leq n\leq 2N$, suppose $\epsilon_n \sim \mathcal N(0, \sigma^2)$ is an i.i.d white noise and $\mathbb E[x_n\epsilon_n]=0$. Define $y_n=f(x_n) + \epsilon_n$. The first $N$ samples will be the training set and the remainder will be the test set.

Consider a model class $\mathcal M$, such that every model $m\in \mathcal M$ is unbiased and has finite variance. Our loss function is MSE. It's easy to see that the expected training loss is $$MSE_{train}(m)=\sigma^2 + \frac{1}{N}\sum_{n=1}^N\mathbb E\left[(f(x_n)-m(x_n))^2-2m(x_n)\epsilon_n\right]$$ Intuitively, I thought that as the number of training samples grows, the term $\frac{1}{N}\sum_{n=1}^N\mathbb E\left[(f(x_n)-m(x_n))^2\right]$ will approach the model's expected MSE loss, ie.

$$\mathbb E[(f(X)-m(X))^2]=\int_I X(f(X)-m(X))^2dX$$, where $I$ is the support of $X$.

In particular, I am hypothesizing that if $N\to\infty$, then a model trained on the training data will have an equal expected fit of $f$, ie. $\mathbb E[(f(x_n)-m(x_n))^2]$ on any sample $x_n$ for $1\leq n\leq 2N$.

Note this, intuitively, can be true even if $m$ memorizes the training data because, with a large number of samples, it can be said that the unseen data is very close to the data $m$ saw before training.

Here is my attempt to prove it:

If parameters of $m\in\mathcal M$ are independent of $x_1,\dots,x_{N}$, the result is obvious. So, let us assume $m$ is conditioned on $x_1,\dots, x_N$.

Since $m$ has a finite variance, the Law of Large Numbers can be applied for $N$ large enough. I will also use an identity: for random variables $A, B$ with finite mean and variance, we have $\mathbb E[\mathbb E[A|B]]=\mathbb E\left[A\right]$.

\begin{align} \mathbb E\left[\frac{1}{N}\sum_{n=1}^N(f(x_n)-m(x_n))^2|x_1,\dots,x_N\right] &= \frac{1}{N}\sum_{n=1}^N\mathbb E\left[(f(x_n)-m(x_n))^2|x_1,\dots,x_N\right]\\ &=\mathbb E\left[\mathbb E\left[(f(X)-m(X))^2|x_1,\dots,x_N\right]\right]\\ &= \mathbb E\left[(f(X)-m(X))^2\right]\\ &= \frac{1}{N}\sum_{n=N+1}^{2N}\mathbb E\left[(f(x_n)-m(x_n))^2\right] \end{align}

Questions

  1. Is this hypothesis even true? Do I need to impose more restrictions on $f$ and $\mathcal M$ before I can say that?
  2. Is my above attempt at proving this hypothesis correct?
Improve this question
$\endgroup$
13
  • $\begingroup$ If all you want is to show that the term $$\frac{1}{N}\sum_{n=1}^N\mathbb E\left[(f(x_n)-m(x_n))^2\right] $$ converges to $\mathbb E[(f(X)-m(X))^2]$ as $N\to\infty$, then it is immediately true. In fact, something much stronger is true : for any $N\ge1$, you have the equality $$\frac{1}{N}\sum_{n=1}^N\mathbb E\left[(f(x_n)-m(x_n))^2\right] = \mathbb E[(f(X)-m(X))^2]$$ which is clear if you remember that the $x_n$'s are i.i.d. and follow the distribution of $X$. Is it really what you want to prove though ? $\endgroup$
    – StratosFair
    May 25 at 19:44
  • $\begingroup$ $m$ is trained on the training dataset (ie. the parameters of $m$ are conditioned on $x_1,x_2,\dots,x_N$). I think in that case the 2nd equality you suggested is not true, but please correct me if I am wrong. $\endgroup$
    – zigs211567
    May 25 at 19:47
  • $\begingroup$ Also note that the model $m$ is the output of a training algorithm hence is a function of $x_1,\ldots,x_n$ (and usually we will denote it $\hat m$ to highlight the fact that it is a function of the sample), so 1) your summation indices should be $N+1\le n\le 2N$ and 2) we need to know if you are computing the expected MSE over $x_1,\ldots,x_{2N}$, $x_N,\ldots,x_{2N}$ or $x_1,\ldots,x_{N}$ $\endgroup$
    – StratosFair
    May 25 at 19:48
  • $\begingroup$ I think there is a misunderstanding. 1) Why do you think the summation indices need to be in $N+1\leq n\leq 2N$? Could you please clarify what you mean by 2)? Is it the term $\mathbb E[{(m(X)-f(X))^2}]$? $\endgroup$
    – zigs211567
    May 25 at 19:54
  • $\begingroup$ 1) Because $x_1,\ldots,x_N$ are the training sample, so when you compute the MSE you compute the error on the testing sample which if I understood your post correctly should be $x_{N+1},\ldots,x_{2N}$. Regarding my point 2) I am simply asking, since $M_N:=\sum_{n=N+1}^{2N} (f(x_n) - m(x_n))^2$ is a random variable which depends on both the training and testing sample (i.e. depends on $x_1,\ldots,x_{2N}$), when you take the expectation $\mathbb E[M_N]$, should it be understood as $\mathbb E_{x_1,\ldots, x_{2N}}[M_N]$ or something else ? $\endgroup$
    – StratosFair
    May 25 at 19:59

0

Reset to default

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.

Browse other questions tagged or ask your own question.