The Exact Excess-Risk Identity for Binary Classification

Why Disagreement Alone Is Not Enough

Two classifiers can disagree with the optimal decision on the same fraction of the population and still have different risks. The reason is that a wrong decision has different consequences at different feature values: when the conditional probability of either label is close to one half, the decision matters little; when one label is much more likely, choosing the other has a larger cost. The exact excess-risk identity makes this distinction precise.

We consider binary classification with labels $Y\in\{0,1\}$ and a feature vector $X$. A classifier $g$ is a measurable function of $X$ taking values in $\{0,1\}$. Its risk is the probability that its predicted label is incorrect. The key function is the conditional probability of label 1, denoted by $\eta$.

Definition: Let $(X,Y)$ have a joint distribution with $Y\in\{0,1\}$. A version of the regression function is the measurable function $\eta(x)=P(Y=1\mid X=x)$, defined up to sets of $X$-probability zero. For a measurable classifier $g\colon\mathcal X\to\{0,1\}$, its classification risk is $R(g)=P(g(X)\ne Y)$. A Bayes classifier is $g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$. The excess risk of $g$ is $R(g)-R(g^*)$.

The choice to predict 1 when $\eta(x)=1/2$ is a tie convention. Predicting 0 there would also minimize conditional risk. All identities below remain valid with either convention, because a disagreement at a tie receives weight zero. Since the losses are bounded, the risks and expectations used below are finite.

The Pointwise Conditional Calculation

At a fixed feature value $x$, predicting 0 is wrong exactly when $Y=1$, and predicting 1 is wrong exactly when $Y=0$. Thus their conditional error probabilities are $\eta(x)$ and $1-\eta(x)$, respectively. Their difference determines both the Bayes decision and the cost of choosing the other decision.

Result: For any $x$ at which $\eta(x)$ is defined, the conditional risk of predicting $a\in\{0,1\}$ is $r(a,x)=P(a\ne Y\mid X=x)=\eta(x)\mathbf{1}\{a=0\}+(1-\eta(x))\mathbf{1}\{a=1\}$. For the Bayes choice $g^*(x)=\mathbf{1}\{\eta(x)\ge1/2\}$, $r(a,x)-r(g^*(x),x)=|2\eta(x)-1|\mathbf{1}\{a\ne g^*(x)\}$.

To verify the second equality, consider each possible value of $\eta(x)$. If $\eta(x)>1/2$, then $g^*(x)=1$. Predicting 1 has conditional risk $1-\eta(x)$, while predicting 0 has risk $\eta(x)$; the increase from the latter decision is $\eta(x)-(1-\eta(x))=2\eta(x)-1$. If $\eta(x)<1/2$, then $g^*(x)=0$, and predicting 1 increases risk by $(1-\eta(x))-\eta(x)=1-2\eta(x)$. If $\eta(x)=1/2$, both decisions have risk $1/2$. These are exactly the three cases represented by the stated absolute-value expression.

Worked Example: Conditional Cost at a Single Feature Value

Suppose $\eta(x)=0.8$. Then predicting 1 has conditional error probability $1-0.8=0.2$, and predicting 0 has conditional error probability $0.8$. The Bayes choice is 1, so choosing 0 increases conditional risk by $0.8-0.2=0.6$. The identity gives $|2(0.8)-1|=|0.6|=0.6$.

If instead $\eta(x)=0.3$, the Bayes choice is 0. Predicting 1 increases conditional risk from $0.3$ to $0.7$, a difference of $0.4$, which agrees with $|2(0.3)-1|=0.4$. At $\eta(x)=0.5$, either decision has conditional risk $0.5$, and the weight $|2\eta(x)-1|$ is zero.

The Exact Excess-Risk Identity

The pointwise calculation becomes a statement about overall risk by conditioning on $X$ and averaging over its distribution. The result requires no density for $X$, and no assumptions about the form of the feature space beyond those needed to define the conditional probability and measurable classifiers.

Theorem (Exact excess-risk identity): Under the binary classification setup above, for every measurable classifier $g\colon\mathcal X\to\{0,1\}$, $$ R(g)-R(g^*)=E\!\left[|2\eta(X)-1|\mathbf{1}\{g(X)\ne g^*(X)\}\right]. $$

Proof. Write the loss as $\mathbf{1}\{g(X)\ne Y\}$. By the tower property of conditional expectation,

R(g) =E\!\left[E\!\left[\mathbf{1}\{g(X)\ne Y\}\mid X\right]\right] =E[r(g(X),X)].

The same calculation gives $R(g^*)=E[r(g^*(X),X)]$. Subtract these finite expectations and apply the pointwise conditional calculation with $a=g(X)$:

$$ \begin{aligned} R(g)-R(g^*) &=E\!\left[r(g(X),X)-r(g^*(X),X)\right]\\ &=E\!\left[|2\eta(X)-1|\mathbf{1}\{g(X)\ne g^*(X)\}\right]. \end{aligned} $$ \(\square\)

The indicator records whether the classifier disagrees with the Bayes rule at the observed feature value. The nonnegative weight $|2\eta(X)-1|$ measures the conditional penalty for that disagreement. Consequently, the identity is an exact equality, not merely an upper or lower bound.

Worked Example: A Finite Feature Distribution

Let $X$ take values $a,b,c$ with probabilities $0.2,0.5,0.3$, respectively, and let $\eta(a)=0.4$, $\eta(b)=0.6$, and $\eta(c)=0.9$. Consider the classifier that predicts 0 at $a$, 0 at $b$, and 1 at $c$. The Bayes classifier predicts 0, 1, and 1 at those points. Thus the only disagreement is at $b$.

The identity gives excess risk $P(X=b)|2\eta(b)-1|=0.5|1.2-1|=0.1$. Direct calculation checks the result. The classifier’s conditional errors are $0.4,0.6,0.1$, so $R(g)=0.2(0.4)+0.5(0.6)+0.3(0.1)=0.08+0.30+0.03=0.41$.

The Bayes classifier’s conditional errors are $0.4,0.4,0.1$, so $R(g^*)=0.2(0.4)+0.5(0.4)+0.3(0.1)=0.08+0.20+0.03=0.31$. Therefore $R(g)-R(g^*)=0.41-0.31=0.10$, as claimed.

Worked Example: A Threshold Classifier with a Continuous Feature

Let $X$ be uniform on $[0,1]$, and suppose $\eta(x)=x$. The Bayes classifier predicts 1 when $x\ge 1/2$. Consider the classifier $g(x)=\mathbf{1}\{x\ge0.7\}$. The classifiers disagree on $[0.5,0.7)$; choices at interval endpoints do not affect the risk because a uniform distribution assigns them probability zero.

The identity yields $R(g)-R(g^*)=\int_{0.5}^{0.7}(2x-1)\,dx$. An antiderivative is $x^2-x$, so the excess risk is $(0.7^2-0.7)-(0.5^2-0.5)=(-0.21)-(-0.25)=0.04$.

For a direct check, the Bayes risk is $\int_0^{0.5}x\,dx+\int_{0.5}^1(1-x)\,dx=0.125+0.125=0.25$. The proposed classifier’s risk is $\int_0^{0.7}x\,dx+\int_{0.7}^1(1-x)\,dx=0.245+0.045=0.29$. The difference $0.29-0.25=0.04$ agrees with the identity.

Ties and What Zero Excess Risk Means

If $\eta(X)=1/2$, the labels are conditionally equally likely, and either prediction has the same conditional risk. The chosen tie convention can therefore make $g$ and $g^*$ disagree on such points without increasing risk. This is why the identity weights disagreement rather than simply counting it.

Corollary: A classifier $g$ has zero excess risk if and only if $|2\eta(X)-1|\mathbf{1}\{g(X)\ne g^*(X)\}=0$ with probability one. Equivalently, it agrees with the Bayes decision almost surely on the set where $\eta(X)\ne1/2$; disagreements where $\eta(X)=1/2$ are immaterial.

To see the equivalence, the theorem says that the excess risk is the expectation of the displayed nonnegative random variable. A nonnegative random variable has expectation zero if and only if it equals zero almost surely. The product equals zero precisely when there is no disagreement or when its weight is zero. Here the weight is zero exactly at $\eta(X)=1/2$. This conclusion concerns agreement up to probability-zero sets; behavior on feature values never observed under the distribution cannot affect risk.

Worked Example: Disagreement at a Tie

Let $X$ take values $a,b,c$ with probabilities $0.25,0.5,0.25$, and let $\eta(a)=0.5$, $\eta(b)=0.2$, and $\eta(c)=0.8$. With the convention $g^*(x)=\mathbf{1}\{\eta(x)\ge1/2\}$, the Bayes predictions are 1, 0, and 1. Suppose $g$ predicts 0, 1, and 1. It disagrees at both $a$ and $b$, but only $b$ contributes to excess risk.

The identity gives $0.5|2(0.2)-1|+0.25|2(0.5)-1|=0.5(0.6)+0.25(0)=0.30$. Directly, $R(g)=0.25(0.5)+0.5(0.8)+0.25(0.2)=0.125+0.4+0.05=0.575$. Meanwhile, $R(g^*)=0.25(0.5)+0.5(0.2)+0.25(0.2)=0.125+0.1+0.05=0.275$. Their difference is $0.575-0.275=0.30$.

Common Pitfall and Interpretation

A common mistake is to say that excess risk equals the probability of disagreeing with the Bayes classifier. The identity shows why this is generally false: disagreement at different feature values is weighted differently. In the finite example above, disagreement occurs with probability $0.5$, but excess risk is $0.1$, because the disagreement is at a point where $|2\eta-1|=0.2$. In the tie example, the total disagreement probability is $0.75$, while excess risk is $0.30$; the tie disagreement contributes nothing.

The weight always lies between zero and one, so the identity also implies $0\le R(g)-R(g^*)\le P(g(X)\ne g^*(X))$. But the unweighted disagreement probability alone does not determine excess risk. For fixed disagreement probability, disagreements concentrated near $\eta=1/2$ have little cost, whereas disagreements at points with $\eta$ far from $1/2$ have greater cost. This weighted view is useful whenever classification rules are compared: it separates where they differ from how costly those differences are under the data distribution.

Check Your Understanding

Use the identity and the conditional-risk calculation to answer each question.

If $\eta(x)=0.65$ and a classifier predicts 0, what is its conditional excess risk at $x$?
Why does disagreement with the chosen Bayes classifier at a point where $\eta(x)=1/2$ contribute zero to excess risk?
For a classifier that disagrees with the Bayes rule on a set $A$, write its excess risk as an expectation using an indicator of $A$.
Does zero excess risk require agreement with the chosen Bayes classifier at every feature value? Explain the role of ties and probability-zero sets.
Can two classifiers with the same probability of disagreement with the Bayes rule have different excess risks? Explain using the weight in the identity.