Expected vs. empirical risk

The expected risk is the average loss over the true data distribution: $R(f)={\mathbb{E}}_{(\mathbf{x},y)\sim \mathcal{D}}[L(y,f(\mathbf{x}))]$. It is what we truly want to be small — but we cannot compute it because $\mathcal{D}$ is unknown.

The empirical risk replaces the expectation with an average over the training sample: ${\hat{R}}_n(f)=\frac{1}{n}{\sum }_{i}L(y_i,f({\mathbf{x}}_i))$. By the law of large numbers, ${\hat{R}}_n(f)\to R(f)$ as $n\to \infty$ for any fixed $f$.

The catch: after we *choose* $f$ to make ${\hat{R}}_n$ small, it is no longer a fair estimate of $R(f)$ for that $f$. This is precisely why training error underestimates test error, and why we need held-out data.