# Limit of expected empirical risk as the number of samples grow

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?
• 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 ? May 25 at 19:44
• $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. May 25 at 19:47
• 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}$ May 25 at 19:48
• 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}]$? May 25 at 19:54
• 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 ? May 25 at 19:59