Bayes rules identify the irreducible part of prediction. Excess risk is the mathematical scale on which a learned rule is compared with this optimal decision.
Conditional risk and Bayes rules
The Bayes rule minimizes conditional risk pointwise. This converts a global optimization problem into a family of ordinary optimization problems indexed by \(x\).
Definition. For a predictor \(a=f(x)\), the conditional risk is \[ L(a,x)=\mathbb E\{\ell(a,Y)\mid X=x\}. \] A Bayes rule is any measurable \(f^*\) satisfying \(f^*(x)\in\operatorname*{argmin}_{a\in\mathcal A_0}L(a,x)\) for \(P_X\)-almost every \(x\).
Theorem. If a measurable pointwise minimizer \(f^*\) exists, then \(f^*\) minimizes \(R(f)\) over all measurable predictors.
Proof. By the tower property, \[ R(f)=\mathbb E\,L(f(X),X). \] For almost every \(x\), \(L(f^*(x),x)\le L(f(x),x)\). Integrating over \(P_X\) gives \(R(f^*)\le R(f)\).
Regression under squared loss
Under squared loss, the Bayes rule is the regression function and excess risk is an \(L^2(P_X)\) distance.
Theorem. For \(\ell(a,y)=(a-y)^2\), the Bayes rule is \(m(x)=\mathbb E(Y\mid X=x)\), and \[ R(f)-R(m)=\mathbb E\{f(X)-m(X)\}^2. \]
Proof. Write \[ Y-f(X)=Y-m(X)+m(X)-f(X). \] After squaring and conditioning on \(X\), the cross term vanishes because \(\mathbb E\{Y-m(X)\mid X\}=0\). This yields the displayed identity.
Remark. This identity explains why nonparametric regression theory is often \(L^2(P_X)\) approximation theory plus stochastic control.
Classification under zero-one loss
In binary classification, only the sign relative to \(1/2\) matters.
Definition. Let \(Y\in\{0,1\}\) and \(\eta(x)=P(Y=1\mid X=x)\). For zero-one loss, the Bayes classifier is \[ g^*(x)=\mathbf 1\{\eta(x)\ge1/2\}. \]
Theorem. For any classifier \(g\), \[ R(g)-R(g^*)=\mathbb E\left[|2\eta(X)-1|\mathbf 1\{g(X)\ne g^*(X)\}\right]. \]
Proof. Condition on \(X=x\). The conditional error of predicting \(1\) is \(1-\eta(x)\), and the conditional error of predicting \(0\) is \(\eta(x)\). Choosing the smaller gives the Bayes error. If \(g\) disagrees with \(g^*\), it chooses the larger conditional error, and the increase is \(|(1-\eta(x))-\eta(x)|=|2\eta(x)-1|\). Integrate over \(X\).
Margin and noise
Classification is easier when \(\eta(X)\) is usually far from \(1/2\).
Definition. The Tsybakov margin condition with exponent \(\alpha>0\) is \[ P_X(0<|\eta(X)-1/2|\le t)\le C t^\alpha,\qquad t>0. \]
Remark. The condition says there is little probability mass near the decision boundary. It is one source of fast rates because classification mistakes near the boundary are the only mistakes that can have small excess-risk cost.
Conditional risk as a calibration device
Every loss determines both an optimal target and a geometry of regret. It is therefore incorrect to speak of “the” regression function without specifying the loss: squared, absolute, quantile, and logarithmic losses elicit different conditional functionals.
Definition. A loss \(\ell(a,y)\) elicits a functional \(T\) if \[ T(Q)=\operatorname*{argmin}_{a}\int\ell(a,y)\,Q(\mathrm{d}y) \] for every distribution \(Q\) in its domain. The conditional Bayes rule is then \(f^*(x)=T(P_{Y\mid X=x})\).
Example. For \(\tau\in(0,1)\), the pinball loss \[ \rho_\tau(u)=u\{\tau-\mathbf 1(u<0)\} \] elicits a \(\tau\)-quantile. Indeed, at continuity points, \[ \frac{\mathrm{d}}{\mathrm{d}a}\mathbb E\rho_\tau(Y-a) =F_Y(a)-\tau, \] so a minimum occurs where \(F_Y(a-)\le\tau\le F_Y(a)\). Thus conditional quantile regression is Bayes prediction under an asymmetric absolute loss.
Bregman losses and conditional means
Definition. If \(\phi\) is differentiable and strictly convex on a convex set, its Bregman divergence is \[ D_\phi(y,a)=\phi(y)-\phi(a)-\langle\nabla\phi(a),y-a\rangle. \]
Theorem. Suppose the required expectations exist. Under loss \(D_\phi(Y,a)\), the conditional mean \(m(x)=\mathbb E(Y\mid X=x)\) is the unique Bayes action, and \[ \mathbb E\{D_\phi(Y,a)\mid X=x\} = \mathbb E\{D_\phi(Y,m(x))\mid X=x\}+D_\phi(m(x),a). \]
Proof. Expand both divergences. The terms involving \(\phi(Y)\) cancel, and \(\mathbb E(Y-m(x)\mid X=x)=0\). The remaining difference is exactly \(\phi(m)-\phi(a)-\langle\nabla\phi(a),m-a\rangle=D_\phi(m,a)\), which is nonnegative and vanishes only at \(a=m\) under strict convexity.
Binary classification with asymmetric costs
Proposition. Suppose a false positive costs \(c_{10}>0\) and a false negative costs \(c_{01}>0\). The conditional risks of actions \(1\) and \(0\) are respectively \[ c_{10}\{1-\eta(x)\},\qquad c_{01}\eta(x). \] Hence the Bayes classifier is \[ g_c^*(x)=\mathbf 1\!\left\{\eta(x)\ge \frac{c_{10}}{c_{01}+c_{10}}\right\}. \]
Proof. Choose action \(1\) precisely when \(c_{10}(1-\eta)\le c_{01}\eta\), and rearrange. The usual threshold \(1/2\) is recovered only when the two error costs agree.
Plug-in classifiers and regression error
Theorem. Let \(\widehat\eta:\mathcal X\to[0,1]\) and \(\widehat g=\mathbf1\{\widehat\eta\ge1/2\}\). Then \[ R(\widehat g)-R(g^*) \le2\,\mathbb E|\widehat\eta(X)-\eta(X)|. \] More generally, if the margin condition with exponent \(\alpha\) holds, then for every \(q\in[1,\infty]\), \[ R(\widehat g)-R(g^*) \le C_{\alpha,q}\, \|\widehat\eta-\eta\|_{L^q(P_X)}^{ \frac{q(1+\alpha)}{q+\alpha}} \] with the exponent interpreted as \(1+\alpha\) when \(q=\infty\).
Proof. On the disagreement set \(\{\widehat g\ne g^*\}\), the two numbers \(\widehat\eta(x)-1/2\) and \(\eta(x)-1/2\) have opposite signs, so \(|\eta(x)-1/2|\le|\widehat\eta(x)-\eta(x)|\). The excess-risk identity therefore gives \[ R(\widehat g)-R(g^*)\le2\mathbb E|\widehat\eta-\eta|. \] For the refined bound, put \(e=|\widehat\eta-\eta|\) and split at \(t>0\): \[ \mathbb E\!\left[|2\eta-1|\mathbf1\{\widehat g\ne g^*\}\right] \le 2tP(0<|\eta-1/2|\le t)+2\mathbb E[e\mathbf1(e>t)]. \] The first term is at most \(2Ct^{1+\alpha}\). Hölder and Markov bound the second by a constant times \(\|e\|_q^q t^{1-q}\). Balancing the two terms yields the displayed exponent.
Multiclass Bayes decisions
Proposition. If \(Y\in\{1,\ldots,K\}\), let \(\eta_k(x)=P(Y=k\mid X=x)\). Under zero-one loss, \[ g^*(x)\in\operatorname*{argmax}_{1\le k\le K}\eta_k(x), \qquad R(g^*)=1-\mathbb E\max_k\eta_k(X). \] For a cost matrix \(C=(C_{ak})\), the Bayes action minimizes \(\sum_k C_{ak}\eta_k(x)\).
Proof. The conditional zero-one risk of predicting \(a\) is \(1-\eta_a(x)\); minimizing it is equivalent to maximizing \(\eta_a(x)\). Replacing \(\mathbf1\{a\ne k\}\) by \(C_{ak}\) gives the second assertion.
Strong convexity and quadratic regret
Proposition. Suppose \(a\mapsto L(a,x)\) is \(\lambda\)-strongly convex for almost every \(x\), with minimizer \(f^*(x)\). Then \[ R(f)-R(f^*)\ge\frac{\lambda}{2} \|f-f^*\|_{L^2(P_X)}^2. \] If its gradient is also \(L\)-Lipschitz, the reverse upper bound \(R(f)-R(f^*)\le(L/2)\|f-f^*\|_2^2\) holds.
Proof. Strong convexity gives \[ L(a,x)\ge L(f^*(x),x)+ \langle\nabla L(f^*(x),x),a-f^*(x)\rangle+ \frac{\lambda}{2}|a-f^*(x)|^2. \] The gradient term vanishes at an interior minimizer. Integrating with \(a=f(x)\) proves the lower bound. The descent lemma gives the upper bound in the same way.
Thus an excess-risk rate is sometimes exactly a parameter-estimation rate, but not always. Classification has a nonsmooth decision boundary, and its conversion depends on the probability mass near that boundary. The later pages on classification margins and surrogate calibration make these conversions quantitative.