Empirical risk minimizers

Fix a sample $S$ and a nonempty class $\mathcal{F}$ of predictors. Its empirical minimum is ${\widehat{R}}_S^{\ast }(\mathcal{F}):={\inf }_{f\in \mathcal{F}}{\widehat{R}}_S(f)\in [0,+\mathrm{\infty }]$. An exact empirical risk minimizer is a predictor $f\in \mathcal{F}$ with ${\widehat{R}}_S(f)={\widehat{R}}_S^{\ast }(\mathcal{F})$. If the infimum is finite but is not attained, no exact minimizer exists. If the infimum is $+\mathrm{\infty }$, nonemptiness implies that every member has infinite empirical risk and is an exact minimizer.

For finite $\eta \ge 0$, a predictor $f\in \mathcal{F}$ is an $\eta$-approximate empirical risk minimizer if either the empirical minimum is $+\mathrm{\infty }$ and $f$ is an exact minimizer, or the empirical minimum is finite and $f$ has finite empirical risk at most ${\widehat{R}}_S^{\ast }(\mathcal{F})+\eta$. The membership requirement $f\in \mathcal{F}$ applies in both branches. Thus the definition never forms $+\mathrm{\infty }+\eta$. When $\eta =0$ and the finite infimum is not attained, no such predictor exists.

For a fixed sample size $m$, a measurable prediction rule with class $\mathcal{F}$ is a jointly measurable evaluation map from the sample space $((\mathsf{X}\times \mathsf{Y}{)}^m,({\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y{)}^{\otimes m})$ and a new instance in $\mathsf{X}$ to $\mathsf{A}$, whose slice at each sample belongs to $\mathcal{F}$. It is an exact or approximate ERM rule when every slice satisfies the corresponding samplewise definition above. This definition asserts no existence of a measurable selector for an arbitrary class.

Supervised prediction problems: fixes the measurable observation and predictor spaces.

Population and empirical risk: defines the samplewise empirical risk being minimized.