Empirical Risk Minimization

Definition

The empirical risk of $f$ on the sample is $R_n(f)=\frac{1}{n}{\sum }_{i=1}^n\ell (X_i,Y_i,f(X_i))$. ERM chooses a function class $\mathcal{F}$ and selects $f_n\in {\mathrm{argmin}}_{f\in \mathcal{F}}{R}_n(f)$.

Formula

$$R_n(f_0)\to R(f_0)\text{a.s. for every fixed }{f}_0\text{(LLN, Proposition 6)},\text{but not in general for }{f}_n$$

• Counterexample: memorize the training labels and predict $-1$ elsewhere: $R_n(f_n)=0$, $R(f_n)=0.5$. The losses $\ell (X_i,Y_i,f_n(X_i))$ are not independent because $f_n$ depends on all points.
• Success depends on the function class $\mathcal{F}$: statistical learning theory (Lecture 3) gives conditions under which ERM is consistent.
• ERM with the 0-1 loss is often NP hard; in practice one minimizes convex surrogate losses.

Appears in

• Lecture 1.2, empirical risk
• Lecture 1.2, Proposition 6
• Lecture 1.2, the ERM principle
• Lecture 1.2, counterexample
• Lecture 1.2, exam-style ERM task
• Lecture 2, linear loss minimization with the perceptron
• Lecture 3, ERM over a fixed class and when it succeeds
• Lecture 3, many minimizers in the overparameterized regime
• Lecture 4, stable ERM is consistent
• Lecture 4, ERM with strongly convex loss is stable

Related concepts

• Loss and Risk
• Estimation and Approximation Error
• Consistency