Empirical risk minimization

Empirical risk minimisation (ERM) picks the hypothesis with the lowest training loss: $\hat{f}=\arg {\min }_{f\in \mathcal{H}}{\hat{R}}_n(f)$. Nearly every supervised algorithm in this course is ERM with a particular $\mathcal{H}$ and $L$.

ERM works well when $\mathcal{H}$ is not too rich relative to $n$: then low empirical risk implies low expected risk. With a very rich class, ERM overfits.

Structural risk minimisation adds a complexity penalty — the regularised objective ${\hat{R}}_n(f)+\lambda \Omega (f)$ — to balance fit and simplicity.