Excess-Risk Decomposition for Plug-In Rules

Why Plug-In Rules Can Lose Risk

A plug-in classifier estimates class probabilities or discriminant scores from training data, then uses those estimates in a decision rule. Its errors have two linked ingredients: how far the estimates are from the population quantities, and whether that error changes the chosen class. A noticeable probability error can have no effect when the best class remains best; a much smaller error can change the decision when two classes are nearly tied.

The excess risk isolates the price of estimating rather than knowing the decision rule. The decomposition below makes that price explicit. It also explains why errors near the Bayes boundary deserve particular attention: that is where a small perturbation can change a classification.

Definition: Let $Y\in\{1,\ldots,K\}$ be the class label, $X$ the feature vector, and $\eta_j(x)=P(Y=j\mid X=x)$ the class posterior probabilities. Under zero-one loss, the risk of a classifier $g$ is $R(g)=P\{g(X)\ne Y\}$. A Bayes classifier is $g^*(x)\in\arg\max_j\eta_j(x)$, and its risk $R(g^*)$ is the Bayes error. The excess risk, or regret, of $g$ is $R(g)-R(g^*)$, which is nonnegative. A plug-in rule based on estimates $\hat\eta_j(x)$ is $\hat g(x)\in\arg\max_j\hat\eta_j(x)$. Ties may be resolved by any fixed rule.

If the posterior estimates are based on a random training sample $D$, then $\hat g$ is random too. We can first evaluate its risk conditional on $D$, using an independent test pair $(X,Y)$, and then average over $D$. Unless stated otherwise, bounds below hold for each fixed training sample, so they also hold after averaging over training samples.

Exact Decomposition for Zero-One Loss

Write $j^*(x)$ for a Bayes class and $k(x)=\hat g(x)$ for the class selected by the plug-in rule. Conditional on $X=x$, predicting class $j$ has error probability $1-\eta_j(x)$. Thus the conditional excess risk of predicting $k(x)$, compared with predicting $j^*(x)$, is $\eta_{j^*}(x)-\eta_k(x)$. Integrating over $X$ gives the exact risk decomposition.

R(\hat g)-R(g^*) = E\!\left[\eta_{j^*(X)}(X)-\eta_{\hat g(X)}(X)\right].

This expression is nonnegative pointwise because $j^*(x)$ maximizes the true posterior. It is also more informative than a bare disagreement rate: a wrong choice between nearly tied classes contributes little regret, whereas choosing a class with much smaller posterior probability contributes more.

Worked Example: A Binary Decision Reversal

At a feature value $x$, suppose the true posterior probabilities are $\eta_1(x)=0.56$ and $\eta_2(x)=0.44$, while the fitted probabilities are $\hat\eta_1(x)=0.48$ and $\hat\eta_2(x)=0.52$. The true Bayes class is 1, but the plug-in rule chooses class 2.

The conditional error probability of the Bayes decision is $1-0.56=0.44$. The conditional error probability after the plug-in decision is $1-0.44=0.56$. Therefore the conditional excess risk is $0.56-0.44=0.12$, equivalently $\eta_1(x)-\eta_2(x)=0.12$.

The largest posterior-coordinate error is $\max(0.08,0.08)=0.08$. The true posterior margin is $0.12$, which is no greater than twice this error, $0.16$. The estimates are sufficiently inaccurate to reverse the ordering, but the resulting regret is still limited by the small separation between the true class probabilities.

Posterior Errors and Boundary Margins

The next result separates probability-estimation errors for the two classes involved in a decision. It also gives a uniform bound in terms of the largest coordinate error. Define $\|\hat\eta(x)-\eta(x)\|_\infty=\max_j|\hat\eta_j(x)-\eta_j(x)|$.

Theorem: For a plug-in rule that maximizes $\hat\eta_j(x)$, let $j^*(x)$ be any class maximizing $\eta_j(x)$ and let $k(x)=\hat g(x)$. Then, at every $x$, $$ \eta_{j^*}(x)-\eta_k(x) = \bigl(\eta_{j^*}(x)-\hat\eta_{j^*}(x)\bigr) +\bigl(\hat\eta_{j^*}(x)-\hat\eta_k(x)\bigr) +\bigl(\hat\eta_k(x)-\eta_k(x)\bigr) \leq |\eta_{j^*}(x)-\hat\eta_{j^*}(x)| + |\eta_k(x)-\hat\eta_k(x)| \leq 2\|\hat\eta(x)-\eta(x)\|_\infty. $$

The middle term in the identity is nonpositive because the plug-in rule maximizes the estimated posterior. Dropping that term and bounding the other two by their absolute values proves the inequalities. Taking expectation yields $R(\hat g)-R(g^*)\leq 2E[\|\hat\eta(X)-\eta(X)\|_\infty]$. This is a general bound; it does not require a margin assumption.

Worked Example: Decomposing Multiclass Regret

At a particular $x$, let the true posterior vector be $\eta(x)=(0.60,0.25,0.15)$ and the fitted vector be $\hat\eta(x)=(0.43,0.45,0.12)$. The Bayes class is 1, while the plug-in rule selects class 2.

The exact conditional regret is $0.60-0.25=0.35$. The decomposition by the two relevant coordinates is $(0.60-0.43)+(0.43-0.45)+(0.45-0.25)=0.17-0.02+0.20=0.35$. The negative middle term reflects that the fitted rule ranks its chosen class above the Bayes class.

The largest coordinate error is $0.20$, so the theorem gives the upper bound $2(0.20)=0.40$, which indeed exceeds the regret $0.35$. The bound uses only the largest error, whereas the exact decomposition uses the errors in the two classes that determine the decision.

The posterior margin measures how separated the best class is from its nearest competitor. Write $\eta_{(1)}(x)$ and $\eta_{(2)}(x)$ for the largest and second-largest posterior probabilities, counting ties, and define $\Delta(x)=\eta_{(1)}(x)-\eta_{(2)}(x)$. A small margin means the observation lies near a Bayes decision boundary.

Theorem: Suppose that, for every $x$, $\|\hat\eta(x)-\eta(x)\|_\infty\leq\varepsilon$. If $\hat g(x)$ does not choose a Bayes class, then $\Delta(x)\leq2\varepsilon$. Moreover, $$ R(\hat g)-R(g^*) \leq 2\varepsilon\,P\{\Delta(X)\leq2\varepsilon\}. $$

To prove the first claim, let $j^*$ be a class with largest true posterior and let $k=\hat g(x)$ be a class that is not Bayes-optimal. Since $\hat\eta_k(x)\geq\hat\eta_{j^*}(x)$, $\eta_{j^*}(x)-\eta_k(x)\leq|\eta_{j^*}(x)-\hat\eta_{j^*}(x)|+|\hat\eta_k(x)-\eta_k(x)|\leq2\varepsilon$. Because $k$ is not Bayes-optimal, $\eta_{j^*}(x)-\eta_k(x)\geq\Delta(x)$, so $\Delta(x)\leq2\varepsilon$. At points where the plug-in rule does choose a Bayes class, regret is zero. Elsewhere, regret is at most $2\varepsilon$ by the same inequality, and the point lies in $\{\Delta(X)\leq2\varepsilon\}$. Taking expectations proves the risk bound. $\square$

A useful consequence follows if the margin distribution satisfies $P\{\Delta(X)\leq t\}\leq C t^\alpha$ for all relevant $t>0$, where $C>0$ and $\alpha\geq0$. Substitution gives $R(\hat g)-R(g^*)\leq 2^{\alpha+1}C\varepsilon^{\alpha+1}$. This condition is an assumption about how much feature probability lies near the boundary, not an automatic property of every classification problem.

Conditional-Risk Scores and General Costs

Under unequal misclassification costs, maximizing a posterior probability is not generally the right decision. Let $C_{ij}$ be the cost of predicting class $j$ when the true class is $i$. The conditional risk of action $j$ at $x$ is $r_j(x)=\sum_{i=1}^K\eta_i(x)C_{ij}$. A Bayes action minimizes $r_j(x)$. A plug-in rule can instead compute $\hat r_j(x)=\sum_i\hat\eta_i(x)C_{ij}$ and choose an action minimizing $\hat r_j(x)$.

Theorem: Let $j^*(x)$ minimize $r_j(x)$, and let $\hat k(x)$ minimize $\hat r_j(x)$. For every $x$, $$ 0\leq r_{\hat k}(x)-r_{j^*}(x) \leq |r_{\hat k}(x)-\hat r_{\hat k}(x)| + |r_{j^*}(x)-\hat r_{j^*}(x)| \leq 2\max_j|r_j(x)-\hat r_j(x)|. $$

For the first inequality, $j^*$ minimizes true conditional risk. For the upper bound, insert and subtract the estimated risks: $r_{\hat k}-r_{j^*}=(r_{\hat k}-\hat r_{\hat k})+(\hat r_{\hat k}-\hat r_{j^*})+(\hat r_{j^*}-r_{j^*})$. The middle term is nonpositive because $\hat k$ minimizes estimated risk. Bounding the remaining terms by absolute values proves the result. Averaging gives the corresponding bound on excess risk. $\square$

Worked Example: Why Costs Change the Decision

There are two classes, diseased (1) and healthy (2). Predicting “treat” costs 0 for a diseased patient and 2 for a healthy patient; predicting “do not treat” costs 5 for a diseased patient and 0 for a healthy patient. At $x$, suppose the true disease probability is $0.20$, while its estimate is $0.35$.

Using the true probability, the conditional risks are $r_{\text{treat}}=0.20(0)+0.80(2)=1.60$ and $r_{\text{no treat}}=0.20(5)+0.80(0)=1.00$. The Bayes action is “do not treat.”

Using the estimated probability, the fitted risks are $\hat r_{\text{treat}}=0.35(0)+0.65(2)=1.30$ and $\hat r_{\text{no treat}}=0.35(5)+0.65(0)=1.75$. The plug-in action is “treat.” Its true conditional excess risk is $1.60-1.00=0.60$.

The risk-score decomposition is $1.60-1.00=(1.60-1.30)+(1.30-1.75)+(1.75-1.00)=0.30-0.45+0.75=0.60$. It exposes both action-specific score errors and the estimated preference for the wrong action. In this example, the posterior argmax would not encode the cost-sensitive decision; conditional risks are the relevant scores.

Interpreting Discriminant Scores

The decomposition applies directly when the estimated scores are posterior probabilities or estimated conditional risks. Discriminant scores can also be used if their maximizer gives the same decisions: for example, log-posterior scores $\log\eta_j(x)$ have the same maximizing class as $\eta_j(x)$, when the probabilities are positive. But a difference on the log-score scale is not itself a probability difference or a classification regret. A numerical error bound for arbitrary transformed scores cannot be substituted into the posterior-error theorem without a valid conversion to posterior or risk-score error.

This distinction matters in practice. Two rules may have the same decision boundary but very different score scales. To assess excess risk, the relevant quantities are changes in conditional loss; to study whether a decision flips, score ordering and score margins may suffice. These are related questions, but they are not identical.

Common Pitfall

A common mistake is to equate posterior estimation error, disagreement probability, and excess risk. They are different quantities. Posterior error measures the size of a probability-estimation discrepancy; disagreement records whether the selected class changes; excess risk weights a wrong choice by its conditional loss. A classifier may disagree with the Bayes rule often near a boundary yet have modest excess risk, or have low overall disagreement but incur substantial regret on a few high-margin observations.

The correction is to use the exact conditional regret $\eta_{j^*}(x)-\eta_{\hat g(x)}(x)$ for zero-one loss, or the conditional-risk difference for general costs, and then average it over $X$. Boundary-margin arguments explain where a bounded estimation error can cause disagreement; they do not make all disagreements equally costly.

Key takeaway: Plug-in excess risk is a conditional-loss difference, not merely a measure of parameter error or disagreement. Posterior estimates affect risk through their impact on decisions, and uniformly small errors can change decisions only where the Bayes margin is small.

Check Your Understanding

Use the conditional-regret and margin decompositions to answer these questions.

For zero-one loss, express the conditional excess risk at $x$ in terms of the true posterior probability of the Bayes class and that of the plug-in class.
Why does a plug-in rule’s maximization property make the middle term in the posterior-error decomposition nonpositive?
If the posterior estimates are uniformly within $0.03$ in maximum-coordinate error, what must be true of the posterior margin at any point where the plug-in rule chooses a non-Bayes class?
Under unequal classification costs, which quantities should be compared to choose a Bayes action: posterior probabilities alone or conditional risks? Explain.
Why can a bound on error in log-posterior scores not automatically be used as a bound on excess risk?