Statistical learning formalizes prediction as risk minimization under an unknown data-generating law. The central object is not the fitted model itself, but the excess risk it incurs relative to the best available rule.
Learning problems and losses
A learning problem begins with a sample space, an action space, and a loss that tells us what prediction quality means.
Definition. Let \((\mathcal X,\mathcal A)\) be the feature space, \((\mathcal Y,\mathcal B)\) the response space, and \(\mathcal A_0\) an action space. A predictor is a measurable map \(f:\mathcal X\to\mathcal A_0\). Given a loss \(\ell:\mathcal A_0\times\mathcal Y\to[0,\infty)\) and a distribution \(P\) on \(\mathcal X\times\mathcal Y\), the risk is \[ R(f)=P\ell_f=\int \ell(f(x),y)\,P(\mathrm{d}x,\mathrm{d}y). \] The training sample is usually \(Z_i=(X_i,Y_i)\), \(i=1,\ldots,n\), drawn i.i.d. from \(P\).
Remark. The word model can mean a probabilistic family for \(P\), a class of predictors \(\mathcal F\), or an algorithm. Statistical learning separates these: the distribution generates data, the class restricts candidates, and the algorithm chooses from the class.
Population and empirical risk
The empirical risk is observable; the population risk is the target. The theory is the study of how close these two optimization problems are.
Definition. For a class \(\mathcal F\), define \[ R_n(f)=P_n\ell_f=\frac1n\sum_{i=1}^n \ell(f(X_i),Y_i), \qquad f_{\mathcal F}^*\in\operatorname*{argmin}_{f\in\mathcal F}R(f). \] An empirical risk minimizer satisfies \(R_n(\hat f_n)\le\inf_{f\in\mathcal F}R_n(f)+\eta_n\), where \(\eta_n\ge0\) is optimization error.
Proposition. For any approximate ERM \(\hat f_n\), \[ R(\hat f_n)-R(f_{\mathcal F}^*)\le 2\sup_{f\in\mathcal F}|(P_n-P)\ell_f|+\eta_n. \]
Proof. Let \(f^*=f_{\mathcal F}^*\). Add and subtract empirical risks: \[ R(\hat f_n)-R(f^*)\le (P-P_n)\ell_{\hat f_n} +(P_n\ell_{\hat f_n}-P_n\ell_{f^*})+(P_n-P)\ell_{f^*}. \] The middle term is at most \(\eta_n\) by approximate empirical optimality, and the two remaining terms are bounded by the same uniform deviation.
Excess risk decomposition
Risk decomposes into statistical, approximation, and algorithmic pieces. Keeping the pieces separate prevents one from blaming estimation for a misspecified class or optimization for insufficient data.
Proposition. Let \(f^*\) be the unrestricted Bayes rule, \(f_{\mathcal F}^*\) the best rule in \(\mathcal F\), and \(\hat f_n\) an approximate estimator in \(\mathcal F\). Then \[ R(\hat f_n)-R(f^*)= \{R(\hat f_n)-R(f_{\mathcal F}^*)\} +\{R(f_{\mathcal F}^*)-R(f^*)\}. \] The first term is estimation plus optimization error; the second is approximation error.
Proof. Insert and subtract \(R(f_{\mathcal F}^*)\). No inequality is hidden here: the equality is useful because different assumptions control the two terms.
Remark. Modern learning theory often sharpens the first term by replacing a global complexity of \(\mathcal F\) with a localized complexity near \(f_{\mathcal F}^*\).
Measurability and random classes
The empirical-process notation \(P_n f\) silently assumes enough measurability to take suprema. This is a technical point, but it matters in proofs.
Definition. A class \(\mathcal G\) of measurable functions is \(P\)-Glivenko-Cantelli if \[ \sup_{g\in\mathcal G}|P_ng-Pg|\to0 \] in probability or almost surely. It is \(P\)-Donsker if the empirical process \(\sqrt n(P_n-P)\) indexed by \(\mathcal G\) converges weakly in \(\ell^\infty(\mathcal G)\).
Remark. Learning bounds usually need Glivenko-Cantelli behavior. Distributional refinements, uncertainty quantification, and localized asymptotics need Donsker or related empirical-process control.
Conditional decision problems
Supervised prediction is a family of decision problems indexed by the observed feature. This conditional formulation produces Bayes rules pointwise and explains why different losses target different features of the conditional law \(P_{Y\mid X=x}\).
Definition. A regular conditional distribution \(P_{Y\mid X=x}\) induces the conditional risk \[ r(a,x)=\int_{\mathcal Y}\ell(a,y)\,P_{Y\mid X=x}(\mathrm{d}y). \] A measurable predictor \(f^*\) is a Bayes rule if \[ f^*(x)\in\operatorname*{argmin}_{a\in\mathcal A_0}r(a,x) \quad\text{for }P_X\text{-almost every }x. \]
Proposition. If a measurable Bayes selector \(f^*\) exists, then \(R(f^*)\le R(f)\) for every measurable predictor \(f\).
Proof. By disintegration and the defining pointwise inequality, \[ R(f)-R(f^*) =\int_{\mathcal X}\{r(f(x),x)-r(f^*(x),x)\}\,P_X(\mathrm{d}x)\ge0. \] The argument also shows that equality is possible only where the two actions have equal conditional risk.
Example. For squared loss and \(Y\in L^2(P)\), \[ r(a,x)=\operatorname{Var}(Y\mid X=x)+\{a-\mathbb E(Y\mid X=x)\}^2, \] so \(f^*(x)=\mathbb E(Y\mid X=x)\). For absolute loss, every conditional median is optimal. For binary zero-one loss, \(f^*(x)=\mathbf 1\{\eta(x)\ge1/2\}\), where \(\eta(x)=P(Y=1\mid X=x)\).
Learning rules and sources of randomness
Definition. A learning rule is a measurable map \[ \mathsf A_n:(\mathcal X\times\mathcal Y)^n\longrightarrow\mathcal F, \qquad D_n\longmapsto\hat f_{D_n}. \] Its conditional generalization error is \[ R(\hat f_{D_n})=\mathbb E\!\left[\ell(\hat f_{D_n}(X),Y)\mid D_n\right], \] where \((X,Y)\sim P\) is independent of \(D_n\). Its expected risk is \(\mathbb E_{D_n}R(\hat f_{D_n})\).
The distinction between conditioning on the training data and averaging over repeated training samples is essential. A high-probability risk bound controls the random fitted rule; an expectation bound alone may hide rare catastrophic samples.
Definition. A sequence \(\hat f_n\) is risk consistent over a class of distributions \(\mathcal P\) if, for every \(P\in\mathcal P\), \[ R_P(\hat f_n)-\inf_fR_P(f)\xrightarrow{P}0. \] It is universally consistent when \(\mathcal P\) contains every distribution satisfying only the integrability conditions required by the loss.
From uniform laws to consistency
Theorem. Let \(\mathcal F_n\) be possibly increasing classes, let \(f_n^*\in\operatorname*{argmin}_{f\in\mathcal F_n}R(f)\), and suppose \[ \Delta_n=\sup_{f\in\mathcal F_n}|R_n(f)-R(f)|\xrightarrow{P}0, \qquad \eta_n\xrightarrow{P}0. \] If \(\hat f_n\) is an \(\eta_n\)-approximate ERM over \(\mathcal F_n\), then \[ R(\hat f_n)-\inf_fR(f) \le 2\Delta_n+\eta_n+ \left\{\inf_{f\in\mathcal F_n}R(f)-\inf_fR(f)\right\}. \] Consequently, if the final approximation term tends to zero, \(\hat f_n\) is risk consistent.
Proof. The basic ERM inequality gives \(R(\hat f_n)-R(f_n^*)\le2\Delta_n+\eta_n\). Add \(R(f_n^*)-\inf_fR(f)\), which is exactly the approximation term. Each term on the right converges to zero by assumption.
Remark. This sieve argument exposes a genuine tradeoff. Enlarging \(\mathcal F_n\) decreases approximation error but usually increases \(\Delta_n\). Rates arise by balancing these two quantities, while computation contributes the separate term \(\eta_n\).
Train, validation, and test samples
Proposition. Let \(D_{\mathrm{test}}=\{Z_i'\}_{i=1}^m\) be independent of all training and model-selection operations, and assume \(0\le\ell\le M\). Conditional on the fitted predictor \(\hat f\), \[ \widehat R_{\mathrm{test}}(\hat f)=\frac1m\sum_{i=1}^m\ell_{\hat f}(Z_i') \] is unbiased for \(R(\hat f)\), and \[ P\!\left(\left|\widehat R_{\mathrm{test}}(\hat f)-R(\hat f)\right|>t \,\middle|\,\hat f\right) \le2\exp\!\left(-\frac{2mt^2}{M^2}\right). \]
Proof. Conditional on \(\hat f\), the test losses are iid, bounded by \(M\), and have common mean \(R(\hat f)\). Conditional unbiasedness and Hoeffding's inequality give the claims. Independence fails if the test set is repeatedly consulted during model development, in which case the displayed guarantee no longer applies to the finally selected rule.
Randomized prediction
A randomized rule is a Markov kernel \(Q(\mathrm{d}a\mid x)\) from features to actions. Its risk is linear in \(Q\): \[ R(Q)=\int\ell(a,y)\,Q(\mathrm{d}a\mid x)P(\mathrm{d}x,\mathrm{d}y). \] When the action set is convex and \(a\mapsto\ell(a,y)\) is convex, Jensen's inequality shows that the deterministic barycenter \(f_Q(x)=\int a\,Q(\mathrm{d}a\mid x)\) has no larger risk. Randomization nevertheless remains useful for aggregation, PAC-Bayes analysis, mixed decisions, and nonconvex action spaces.
Prerequisites and interfaces
The uniform laws used here are developed in empirical measures and Glivenko-Cantelli theory. Conditional Bayes actions and randomized rules are treated abstractly in decision problems, rules, and risks. The next pages turn the decomposition above into quantitative bounds through concentration and complexity.