Proof that the expected MSE is smaller in training than in test This is Exercise 2.9 (p. 40) of the classic book "The Elements of Statistical Learning", second edition, by Hastie, Tibshirani and Friedman. In the book, it's mentioned that this exercise was brought to the authors' attention by Ryan Tibshirani, from a homework assignment by Andrew Ng.
Ex. 2.9. Consider a linear regression model with $p$ parameters, fit by least squares to a set of training data $(x_1,y_1),\dots,(x_N,y_N)$ drawn at random from a population. Let $\hat{\beta}$ be the least squares estimate. Suppose we have some test data $(\tilde{x}_1,\tilde{y}_1),\dots,(\tilde{x}_M,\tilde{y}_M)$ drawn at random from the same population as the training data. If $R_{tr}(\beta)=\frac{1}{N}\sum_{i=1}^N(y_i-\beta^T x_i)^2$ and $R_{te}(\beta)=\frac{1}{M}\sum_{i=1}^M(\tilde{y}_i-\beta^T \tilde{x}_i)^2$, prove that
$$
  \mathrm{E}[R_{tr}(\hat{\beta})]\leq\mathrm{E}[R_{te}(\hat{\beta})],
$$
where the expectations are over all that is random in each expression.
 A: I think the above answer is correct, but let me just explain some of the intuition for this problem, which helps us generalize it to a broader scope of models. First we'll assume that $N = M$, for notational convenience. This assumption allows us to assume that the training set and test set are drawn from the same distribution. 
Let $L(m, y)$ be the loss of the model $m$ on a data set $y$. Let $\mathcal{M}$ be the set of all models (not necessarily linear).
Now define $m_x$ to be a model which optimizes the loss on data set $x$, that is, $L(m_x, x) \le  L(m, x)$ for all models $m \in \mathcal{M}$. 
Let the data set $x$ and the data set $y$ be drawn independently from a distribution $\mathcal{D}$. The LHS in the original problem represents the average value of $L(m_x, x)$ whereas the RHS represents the average value of $L(m_x, y)$. This is hard to compare; it's possible for $L(m_x, x)$ to be larger than $L(m_x, y)$ because $y$ might just be an "easier" dataset than $x$. However, we can see that the average value of $L(m_x, y)$ is the same as the average value of $L(m_y, x)$ because $x$ and $y$ are independent. Now, the comparison is easy. The average value of $L(m_x, x)$ is less than or equal to the average value of $L(m_y, x)$ because $L(m_x, x)$ is always less than $L(m_y, x)$, and we may conclude. 
A: The short answer is this:
\begin{equation}
    \text{E}[R_{tr}(\hat{\beta})] \le \text{E} [R_{tr} (\text{E} \hat{\beta})] = \text{E} [R_{te} (\text{E} \hat{\beta})] \le \text{E} [R_{te}(\hat{\beta})]
\end{equation}
Now I explain this in more details.

*

*Proving the left inequality. $\hat{\beta}$ comes from the following:

\begin{equation}
    \hat{\beta} = \text{arg} \min_{\beta'} R_{tr}(\beta')
\end{equation}
This implies that for any fix $\beta$:
\begin{equation}
    R_{tr} (\hat{\beta}) \le R_{tr} (\beta)
\end{equation}
Taking the expectation of both sides:
\begin{equation}
    \text{E} [R_{tr} (\hat{\beta})] \le \text{E} [R_{tr} (\beta)]
\end{equation}
$\hat{\beta}$ is a random variable (which depends on the training data), we can take the expectation, so we get $\text{E}\hat{\beta}$ which is a fix, non-random vector. Substituting into the above inequality we get what we wanted to prove:
\begin{equation}
    \text{E} [R_{tr} (\hat{\beta})] \le \text{E} [R_{tr} (\text{E}\hat{\beta})]
\end{equation}


*Proving the equation in the middle. For any fix $\beta$:

\begin{equation}
    \text{E} [R_{tr} (\beta)] = \frac 1N \sum_{i=1}^{N} \text{E} [(y_i - \beta^{T} x_i) ^{2}] = \text{E} [(Y - \beta^{T} X)^{2}]
\end{equation}
\begin{equation}
    \text{E} [R_{te} (\beta)] = \frac 1M \sum_{i=1}^{M} \text{E} [(\widetilde{y_i} - \beta^{T} \widetilde{x_i}) ^{2}] = \text{E} [(Y - \beta^{T} X)^{2}]
\end{equation}
This is because both the train and the test data come from the same distribution. So for any fix $\beta$, $\text{E} [R_{tr} (\beta)] = \text{E} [R_{te} (\beta)]$. Since $\text{E}\hat{\beta}$ is a fix vector, we're done with this part.


*Proving the right inequality. For this we use the fact that the training data and the test data are independent. Thus $\hat{\beta}$ and the test data are also independent. For this part, just forget about the training data. Think of $\hat{\beta}$ as a random vector independent from the (test) data.

\begin{equation}
    \text{E} [R_{te}(\hat{\beta})] = \text{E} (Y - \hat{\beta}^{T} X) ^{2} = \text{E} \text{E} \left( (Y - \hat{\beta}^{T} X) ^{2} | X,Y\right)
\end{equation}
\begin{aligned}
    \text{E} \left( (Y - \hat{\beta}^{T} X)^{2} | X, Y \right) =& \text{E} \left( Y^2 - 2Y\hat{\beta}^{T} X + (\hat{\beta}^T X)^{2} | X, Y \right)\\
    =& Y^2 - 2Y \text{E}(\hat{\beta}^{T}) X + X^{T} \text{E}(\hat{\beta} \hat{\beta}^T) X\\
    =& Y^2 - 2Y \text{E}(\hat{\beta}^{T}) X + X^{T} [ \text{E}\hat{\beta} \cdot \text{E}\hat{\beta}^T + \text{Cov}(\hat{\beta}) ] X\\
    =& Y^2 - 2Y \text{E}(\hat{\beta}^{T}) X + (\text{E}\hat{\beta}^T) X X^{T} (\text{E} \hat{\beta}) + X^{T} \text{Cov}(\hat{\beta}) X
\end{aligned}
Since the covariance matrix is positive semi-definite, $X^{T} \text{Cov}(\beta) X \ge 0$
\begin{aligned}
    \text{E} \left( (Y - \hat{\beta}^{T} X)^{2} | X, Y \right) \ge& Y^2 - 2Y \text{E}(\hat{\beta}^{T}) X + (\text{E}\hat{\beta}^T) X X^{T} (\text{E}) \hat{\beta}\\
    \text{E} \left( (Y - \hat{\beta}^{T} X)^{2} | X, Y \right) \ge& (Y - \text{E}(\hat{\beta}^{T}) X) ^{2}\\
    \text{E} \text{E} \left( (Y - \hat{\beta}^{T} X)^{2} | X, Y \right) \ge& \text{E} (Y - \text{E}(\hat{\beta}^{T}) X)^{2}\\
    \text{E} (Y - \hat{\beta}^{T} X) ^{2} \ge& \text{E} (Y - \text{E}(\hat{\beta}^{T}) X)^{2}\\
    \text{E} R_{te}(\hat{\beta}) \ge& \text{E} R_{te}(\text{E} \hat{\beta})
\end{aligned}
A: This is an interesting problem which makes you think about what is random in your computations. Here is my take.
The least squares estimate $\hat{\beta}$ is the solution of
$$
  \arg \min_{\beta\in\mathbb{R}^{p+1}} \sum_{k=1}^N (y_k-\beta^T x_k).
$$
Hence, if you consider the random training data $(X_1,Y_1),\dots,(X_n,Y_n)$ as IID pairs from some unknown distribution function $F_{X,Y}$, we can imagine the random vector $\hat{\beta}$ (the least squares estimator) as some functional $\hat{\Psi}[(X_1,Y_1),\dots,(X_n,Y_n)]$, with suitable measurability conditions, which satisfies
$$
  \sum_{k=1}^N (Y_k-\hat{\beta}^T X_k)^2 \leq \sum_{k=1}^N (Y_k-\beta^T X_k)^2, \qquad (*) 
$$
almost surely, for every random vector $\beta$.
The symmetry of the IID assumption yields that
$$
  \frac{1}{N}\sum_{k=1}^N \mathrm{E}[(Y_k-\beta^T X_k)^2] = \mathrm{E}[(Y_i-\beta^T X_i)^2],
$$
for $i=1,\dots,N$, and every random vector $\beta$.
Therefore, dividing by $N$ and taking expectations in $(*)$, we have that
$$
  \mathrm{E}[(Y_i-\hat{\beta}^T X_i)^2] \leq \mathrm{E}[(Y_i-\beta^T X_i)^2], \qquad (*') 
$$
for $i=1,\dots,N$, and every random vector $\beta$.
The key point here is that, since $(*')$ holds for every random vector $\beta$, it must hold for the random vector
$$
  \beta = \frac{1}{||X_i||^2}\left(Y_iX_i - \tilde{Y}_jX_i + X_i\tilde{X}_j^T\hat{\beta} \right),
$$
for any choice of $j=1,\dots,M$. Using this $\beta$ in $(*')$ we have that
$$
  \mathrm{E}[(Y_i-\hat{\beta}^T X_i)^2] \leq \mathrm{E}[(\tilde{Y}_j-\hat{\beta}^T \tilde{X_j})^2],
$$
for every $i=1,\dots,N$, and every $j=1,\dots,M$.
The last inequality and the IID assumption (in the same way we used it before) imply that
$$
  \frac{1}{N} \sum_{k=1}^N \mathrm{E}[(Y_k-\hat{\beta}^T X_k)^2] \leq \frac{1}{M} \sum_{k=1}^M \mathrm{E}[(\tilde{Y}_k-\hat{\beta}^T \tilde{X}_k)^2], 
$$
so
$$
  \mathrm{E}[R_{tr}(\hat{\beta})] \leq \mathrm{E}[R_{te}(\hat{\beta})].
$$
${}$
