Empirical risk minimization

Empirical risk minimization chooses a hypothesis that minimizes the average loss on the observed data.

The empirical risk of a hypothesis $h$ on observations $z_1,\dots ,z_n$ is the sample-average loss

A loss function assigns a numerical penalty to a prediction and its observed outcome. Its expected value is the population risk optimized by a statistical learning procedure.

The population risk of a prediction rule is its expected loss on a fresh observation from the target probability distribution.

Given a hypothesis class $\mathcal{H}$ and a loss function $\ell$, its loss class is the function classIt lets properties of a learning problem be studied through the random fluctuations of the losses themselves.

For a classifier $h$ and a labelled example $z=(x,y)$, the misclassification loss isIt is also called zero-one loss because it is zero for a correct prediction and one for an incorrect prediction.

The misclassification risk of a classifier is its expected misclassification loss,

For a random classifier $C$ determined by training information $\mathcal{T}$, and an independent test pair $(X,Y)$, its conditional misclassification risk is $L(C)=\mathbb{P}(C(X)\ne Y\mid \mathcal{T})$. It is itself a training-dependent random variable. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$.

On labelled examples $Z_1,\dots ,Z_n$, the empirical misclassification risk isAn empirical risk minimizer chooses a classifier attaining the smallest value over its hypothesis class.

If $h^{\ast }$ minimizes the population risk over a hypothesis class, the excess risk of $h$ is the nonnegative difference $R(h)-R(h^{\ast })$.

For data $(X_i,Y_i)$ and predictions $h_{\beta }(X)={\beta }^{T}X$, it is convenient to writeIts gradient is