Splitting Plug-In Error at a Margin Level

Why Split Classification Error by Margin?

A plug-in classifier estimates the conditional probability of class 1 and assigns a label by comparing that estimate with one half. Its predictions can disagree with the Bayes classifier when the estimate is inaccurate, but not every estimation error is equally consequential. An error near the decision threshold can change a label when the true conditional probability is close to one half; the same-sized error far from the threshold may not change the label at all.

A margin split formalizes this distinction. Feature points with small true margin are handled by bounding the regret they could contribute. For the remaining points, a disagreement is possible only if the regression estimation error is large enough. The resulting bound separates these two sources of difficulty.

Definition: Let $X$ be the feature vector and $Y\in\{0,1\}$ the binary response. Write $\eta(x)=P(Y=1\mid X=x)$ for the regression function, and let $\hat\eta(x)$ be a measurable estimate taking values in $[0,1]$. Define the true margin and absolute estimation error by $$ \Delta(x)=|2\eta(x)-1|,\qquad e(x)=|\hat\eta(x)-\eta(x)|. $$ The Bayes classifier is $g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$, and the plug-in classifier is $\hat g(x)=\mathbf{1}\{\hat\eta(x)\ge 1/2\}$. Both rules assign class 1 at a tie.

The margin $\Delta(x)$ ranges from 0 to 1. It is zero at the Bayes decision threshold and grows as $\eta(x)$ moves away from one half. The estimation error $e(x)$ measures the pointwise distance between the estimated and true regression functions.

For a classifier $g$, let $R(g)=P(g(X)\ne Y)$ be its misclassification risk. The standard exact excess-risk identity for binary classification is $$ R(\hat g)-R(g^*)=E_X\!\left[\Delta(X)\mathbf{1}\{\hat g(X)\ne g^*(X)\}\right]. $$ Indeed, conditional on $X=x$, predicting 0 has error probability $\eta(x)$, while predicting 1 has error probability $1-\eta(x)$; their difference in risk is $|2\eta(x)-1|=\Delta(x)$. Thus only disagreements contribute to excess risk, weighted by the true margin.

Why Disagreement Requires Error Relative to the Margin

The key geometric fact is that changing the predicted class requires crossing the threshold $1/2$. The estimate must therefore be at least as far from the truth as the distance from the true regression value to that threshold.

Lemma: If $\hat g(x)\ne g^*(x)$, then $$ e(x)\ge |\eta(x)-1/2|=\Delta(x)/2. $$

To verify the lemma, first suppose $\eta(x)>1/2$. Then $g^*(x)=1$, so disagreement means $\hat\eta(x)<1/2$. Consequently, $$ |\hat\eta(x)-\eta(x)|=\eta(x)-\hat\eta(x)>\eta(x)-1/2. $$ If instead $\eta(x)<1/2$, disagreement means $\hat\eta(x)\ge 1/2$, and hence $$ |\hat\eta(x)-\eta(x)|=\hat\eta(x)-\eta(x)\ge 1/2-\eta(x). $$ When $\eta(x)=1/2$, the right side of the claimed inequality is zero, so the inequality holds automatically. Since $\Delta(x)/2=|\eta(x)-1/2|$, the lemma follows in every case. $\square$

The Margin-Level Regret Bound

Choose a threshold $t>0$. Call points with $\Delta(x)\le 2t$ low-margin points. On the remaining points, $\Delta(x)>2t$; if the classifiers disagree there, the lemma implies $e(x)\ge\Delta(x)/2>t$. This is the basis for the split.

Theorem: For any measurable $\hat\eta:X\to[0,1]$ and any $t>0$, $$ R(\hat g)-R(g^*)\le E_X\!\left[\Delta(X)\mathbf{1}\{\Delta(X)\le 2t\}\right] + E_X\!\left[2\Delta(X)\mathbf{1}\{e(X)>t\}\right]. $$

Proof. Start from the exact excess-risk identity. At any feature point with $\Delta(x)\le 2t$, the disagreement contribution is at most $\Delta(x)$, whether or not the classifiers actually disagree. At a point with $\Delta(x)>2t$, disagreement implies $e(x)\ge\Delta(x)/2>t$, by the lemma. Therefore the pointwise inequality $$ \Delta(x)\mathbf{1}\{\hat g(x)\ne g^*(x)\} \le \Delta(x)\mathbf{1}\{\Delta(x)\le 2t\} + 2\Delta(x)\mathbf{1}\{e(x)>t\} $$ holds: in the low-margin region the first term covers the left side, and in the high-margin region any nonzero left side is covered by the second. Taking expectations gives the result. The second term is written with the conservative weight $2\Delta(x)$; the proof only needs the weight $\Delta(x)$ there. $\square$

The two terms play different roles. The first depends on how much margin-weighted probability lies near the Bayes threshold. The second depends on the margin-weighted probability of large regression estimation error. The split is an upper bound, not an exact decomposition: in particular, the second term can count points even if they are low-margin points or if the plug-in classifier predicts correctly there.

Worked Example: A Discrete Feature Distribution

Suppose $X$ takes values $a,b,c$ with probabilities $1/2,1/4,1/4$, respectively. Let the true and estimated regression values be $$ \begin{array}{c|ccc} x & a & b & c\\ \eta(x) & 0.55 & 0.90 & 0.30\\ \hat\eta(x) & 0.35 & 0.40 & 0.35 \end{array} $$ Use $t=0.1$ to calculate the bound and the actual excess risk.

At $a$, $\Delta(a)=|1.10-1|=0.10$ and $e(a)=|0.35-0.55|=0.20$. The Bayes classifier predicts 1 and the plug-in classifier predicts 0, so this point is a disagreement. At $b$, $\Delta(b)=|1.80-1|=0.80$ and $e(b)=|0.40-0.90|=0.50$; this is also a disagreement. At $c$, $\Delta(c)=|0.60-1|=0.40$ and $e(c)=|0.35-0.30|=0.05$; both classifiers predict 0.

The low-margin threshold is $2t=0.2$, so only $a$ contributes to the first term: $$ E_X[\Delta(X)\mathbf{1}\{\Delta(X)\le 0.2\}] =\frac12(0.10)=0.05. $$ For the second term, $e(a)=0.20>0.1$ and $e(b)=0.50>0.1$, while $e(c)=0.05$ is not greater than $0.1$. Thus $$ E_X[2\Delta(X)\mathbf{1}\{e(X)>0.1\}] =\frac12(2\cdot0.10)+\frac14(2\cdot0.80) =0.10+0.40=0.50. $$ The bound is $0.05+0.50=0.55$. The actual excess risk counts only the two disagreements: $$ R(\hat g)-R(g^*)=\frac12(0.10)+\frac14(0.80)=0.05+0.20=0.25. $$ The bound is valid but loose. In particular, point $a$ contributes to both terms: being low-margin does not remove it from the large-error term.

Worked Example: Integrating the Bound Over a Continuous Feature

Let $X$ be uniform on $[0,1]$, let $\eta(x)=0.25+0.5x$, and set $\hat\eta(x)=\eta(x)+0.1$. Both regression functions lie in $[0,1]$. Take $t=0.05$.

Here $\Delta(x)=|2\eta(x)-1|=|x-0.5|$, and $e(x)=0.1$ everywhere. The low-margin condition is $|x-0.5|\le 0.1$. Since $X$ has density 1, $$ E_X[\Delta(X)\mathbf{1}\{\Delta(X)\le 0.1\}] =\int_{0.4}^{0.6}|x-0.5|\,dx =2\int_0^{0.1}u\,du =0.01. $$ The error exceeds $t$ at every point, so the entire feature interval contributes to the second term: $$ E_X[2\Delta(X)\mathbf{1}\{e(X)>0.05\}] =2\int_0^1|x-0.5|\,dx =2\left(2\int_0^{0.5}u\,du\right) =0.50. $$ The bound is therefore $0.01+0.50=0.51$.

For comparison, the Bayes classifier predicts 1 when $x\ge0.5$, while the plug-in classifier predicts 1 when $\eta(x)+0.1\ge0.5$, or $x\ge0.3$. They disagree on $[0.3,0.5)$, up to endpoints of probability zero. The actual excess risk is $$ \int_{0.3}^{0.5}(0.5-x)\,dx =\frac{(0.2)^2}{2} =0.02. $$ The second bound term is deliberately conservative: it includes every point where the estimation error exceeds $t$, not just the points where the classifiers disagree.

Choosing a Threshold and Reading the Bound

The threshold $t$ determines how the bound divides its work. Increasing $t$ enlarges the low-margin region $\{\Delta\le 2t\}$, while shrinking the large-error region $\{e>t\}$. Decreasing $t$ has the opposite effect. A useful threshold balances the margin contribution against the large-error contribution; the best balance depends on the joint behavior of the true margin and the estimation error.

The next example shows how the bound changes with the threshold and why it need not equal the actual regret. Its calculation uses the same two terms as the theorem, including all feature points whose estimation error exceeds the chosen threshold.

Worked Example: Comparing Two Threshold Choices

Let $X$ take values $a,b$ with probabilities $0.6,0.4$. At $a$, let $\eta(a)=0.525$ and $\hat\eta(a)=0.495$. At $b$, let $\eta(b)=0.70$ and $\hat\eta(b)=0.45$. Thus $(\Delta(a),e(a))=(0.05,0.03)$ and $(\Delta(b),e(b))=(0.40,0.25)$. Both points are disagreements.

The actual excess risk is $$ 0.6(0.05)+0.4(0.40)=0.03+0.16=0.19. $$ First choose $t=0.1$. The low-margin threshold is $2t=0.2$, so only $a$ enters the margin term, which equals $0.6(0.05)=0.03$. Only $b$ has error greater than $0.1$, giving a large-error term of $0.4(2\cdot0.40)=0.32$. The bound is $0.03+0.32=0.35$.

Now choose $t=0.3$. The low-margin threshold is $0.6$, so both points enter the margin term: $$ 0.6(0.05)+0.4(0.40)=0.19. $$ Neither estimation error exceeds $0.3$, so the second term is zero. This gives the bound $0.19$, equal to the actual excess risk in this example. The equality is specific to these values, not a general property of the method.

A Common Pitfall

The most common error in applying the bound is to restrict the large-error term to feature points where a disagreement occurs, or to remove low-margin points from that term after they have contributed to the first term. The theorem does neither: its second term is the expectation over the full event $\{e(X)>t\}$. A point may contribute to both terms. This overlap makes the inequality easy to apply and does not invalidate it; it can simply make the bound looser.

The continuous example makes the accounting explicit. Since $e(x)=0.1>0.05$ for every $x$, the large-error term integrates $2\Delta(x)$ over all of $[0,1]$, yielding $0.50$. Integrating only over the disagreement interval would not calculate the stated theorem's term. Likewise, a low-margin point with $e(x)>t$ still belongs in the second expectation.

Compute the true margin and estimation error.
For each feature point, calculate $\Delta(x)=|2\eta(x)-1|$ and $e(x)=|\hat\eta(x)-\eta(x)|$.

Set the margin threshold.
For a chosen $t>0$, the low-margin region in this bound is $\Delta(x)\le2t$.

Evaluate both expectations on their stated events.
Use $\Delta\le2t$ for the first term and $e>t$ for the second; do not require disagreement for the second term.

Key takeaway: A plug-in disagreement away from the Bayes threshold requires substantial estimation error. Splitting at $t$ bounds regret by the margin-weighted contribution from $\Delta\le2t$ plus a large-error contribution over every point with $e>t$.

Check Your Understanding

Use the definitions and bound above to answer these questions.

Why does a disagreement at a point with $\Delta(x)>2t$ imply $e(x)>t$?
For a point with $\Delta(x)\le2t$ and $e(x)>t$, which terms of the theorem can include its contribution?
In the continuous example, why is the large-error integral taken over the full interval $[0,1]$?
If $t$ increases, how do the two events in the bound change?
Why can the bound exceed the actual excess risk even when every term has been calculated correctly?