Boundary-Localized Error Bounds for Plug-In Rules

Why Local Accuracy Can Matter More Than Global Accuracy

A plug-in classifier estimates the conditional probability of class 1 and assigns a label according to whether that estimate is above or below one half. Errors in this regression estimate are not equally consequential everywhere. Near the Bayes decision boundary, a small error can reverse the predicted class. Far from the boundary, a larger error may leave the predicted class unchanged. This motivates bounds that focus on a neighborhood of the boundary rather than summarizing regression accuracy over the whole feature space.

The key qualification is that local accuracy alone is not automatically enough. A classifier can be accurate near the boundary and still make a severe mistake far away. We will derive a bound that localizes regret to points where the estimated and Bayes decisions disagree, then state precisely when an error bound on a boundary neighborhood suffices.

Definition: In binary classification, let $Y\in\{0,1\}$, let $X$ be the feature vector, and define the regression function $\eta(x)=P(Y=1\mid X=x)$. The Bayes classifier is $g^*(x)=\mathbf{1}\{\eta(x)\geq 1/2\}$. For an estimate $\hat\eta$, the plug-in classifier is $\hat g(x)=\mathbf{1}\{\hat\eta(x)\geq 1/2\}$. Define the regression error $e(x)=|\hat\eta(x)-\eta(x)|$, the margin gap $\Delta(x)=|2\eta(x)-1|$, and the boundary neighborhood $N(t)=\{x:\Delta(x)\leq t\}$, for $t\geq0$.

The gap $\Delta(x)$ is twice the distance from $\eta(x)$ to the threshold. Thus $N(t)$ contains points whose conditional class probabilities are close enough to one half that a relatively small regression error might change the decision. All expectations below are over the feature distribution. If $\hat\eta$ is estimated from training data, the statements can first be applied conditional on that data, treating $\hat\eta$ as fixed.

A Self-Localized Regret Bound

For any classifier $g$, write its risk as $R(g)=P\{g(X)\ne Y\}$. The exact excess-risk identity for binary classification is $R(\hat g)-R(g^*)=E[\Delta(X)\mathbf{1}\{\hat g(X)\ne g^*(X)\}]$. It shows that only disagreements contribute to regret, and weights each disagreement by its margin gap.

Theorem (self-localized plug-in bound): For any measurable estimate $\hat\eta$ and the plug-in classifier defined above, $$ R(\hat g)-R(g^*)\leq 2E\!\left[e(X)\mathbf{1}\{\Delta(X)\leq 2e(X)\}\right]. $$

Proof. Fix a feature value $x$. If the classifiers disagree, the two regression values $\eta(x)$ and $\hat\eta(x)$ lie on opposite sides of the threshold $1/2$, allowing equality according to the stated threshold rule. The distance between those values is therefore at least the distance from $\eta(x)$ to $1/2$: $e(x)\geq|\eta(x)-1/2|=\Delta(x)/2$. Consequently, disagreement implies $\Delta(x)\leq2e(x)$. On a disagreement, the pointwise regret contribution $\Delta(x)$ is at most $2e(x)$; off the disagreement set, the contribution is zero. Applying the excess-risk identity and integrating gives the claimed inequality. $\square$

This bound is localized in a data-dependent way: an error contributes only where the margin gap is no larger than twice that error. It does not charge a large regression error at a point where the plug-in decision remains correct. But the neighborhood in the bound depends on $e(x)$; it is not necessarily a fixed, narrow band around the boundary.

Worked Example: Errors at and Away from the Boundary

Suppose $X$ takes values $a,b,c$ with probabilities $0.2,0.3,0.5$, respectively. Let the true regression values be $\eta(a)=0.49$, $\eta(b)=0.20$, and $\eta(c)=0.90$, and let the estimates be $\hat\eta(a)=0.51$, $\hat\eta(b)=0.10$, and $\hat\eta(c)=0.95$. Compute the regret and the self-localized bound.

At $a$, the Bayes label is 0 and the plug-in label is 1; $e(a)=0.02$ and $\Delta(a)=|0.98-1|=0.02$. At $b$, both labels are 0; $e(b)=0.10$ and $\Delta(b)=0.60$. At $c$, both labels are 1; $e(c)=0.05$ and $\Delta(c)=0.80$. Only $a$ contributes to the exact regret, so $R(\hat g)-R(g^*)=0.2(0.02)=0.004$.

For the bound, the condition $\Delta\leq2e$ holds at $a$, since $0.02\leq0.04$, but not at $b$ or $c$. Hence $2E[e\mathbf{1}\{\Delta\leq2e\}]=2(0.2)(0.02)=0.008$, which indeed bounds the regret $0.004$. The relatively large error at $b$ does not enter this bound: it is too small to overcome the large margin there.

When a Fixed Boundary Neighborhood Suffices

A fixed neighborhood bound is useful when one can ensure the classifier is correct outside that neighborhood. For example, such agreement may follow from an error guarantee that is strong enough away from the boundary. Under this condition, all regret is confined to $N(t)$, where localized regression error can control it.

Theorem (fixed-neighborhood bound): Fix $t\geq0$. If $\hat g(x)=g^*(x)$ for $P_X$-almost every $x\notin N(t)$, then $$ R(\hat g)-R(g^*)\leq \min\left\{tP_X(N(t)),\;2E[e(X)\mathbf{1}\{X\in N(t)\}]\right\}. $$

Proof. By the assumed agreement, the disagreement indicator in the excess-risk identity vanishes outside $N(t)$. Inside $N(t)$, $\Delta(x)\leq t$. Therefore the identity gives $R(\hat g)-R(g^*)\leq tP_X(N(t))$. Also, whenever the classifiers disagree, the threshold argument in the previous proof gives $\Delta(x)\leq2e(x)$. Restricting the identity to $N(t)$ thus gives $R(\hat g)-R(g^*)\leq2E[e(X)\mathbf{1}\{X\in N(t)\}]$. Both inequalities hold, so their minimum is also an upper bound. $\square$

The two terms express complementary controls. The first uses only how much feature probability lies in the boundary neighborhood; the second uses the regression error integrated over that neighborhood. Neither requires a global average error bound, but the agreement assumption outside $N(t)$ is essential.

Worked Example: A Local Error Bound with Correct Decisions Outside

Let $X=a$ with probability $0.25$ and $X=b$ with probability $0.75$. At $a$, let $\eta(a)=0.49$ and $\hat\eta(a)=0.51$. At $b$, let $\eta(b)=0.90$ and $\hat\eta(b)=0.80$. Use $t=0.10$.

At $a$, $\Delta(a)=0.02$, so $a\in N(0.10)$; the classifiers disagree and $e(a)=0.02$. At $b$, $\Delta(b)=0.80$, so $b\notin N(0.10)$; both classifiers assign label 1. Thus they agree outside the neighborhood, as required.

The exact regret is $0.25(0.02)=0.005$. The two theorem bounds are $tP_X(N(t))=0.10(0.25)=0.025$ and $2E[e\mathbf{1}\{X\in N(t)\}]=2(0.25)(0.02)=0.01$. Their minimum, $0.01$, is a valid upper bound on $0.005$. The error $e(b)=0.10$ is not included in the localized error term because $b$ is outside the boundary neighborhood and its decision is correct.

What If There Are Errors Outside the Neighborhood?

Without agreement outside $N(t)$, the fixed-neighborhood theorem cannot be applied. A useful alternative splits the regret into a local contribution and a tail contribution for errors at larger margins. This makes explicit what additional control is needed away from the boundary.

Proposition (local-plus-tail bound): For $t>0$ and $q\geq1$, $$ R(\hat g)-R(g^*)\leq 2E[e(X)\mathbf{1}\{X\in N(t)\}] + \frac{2^q}{t^{q-1}}E[e(X)^q\mathbf{1}\{X\notin N(t)\}]. $$

Proof. Split the excess-risk identity into $N(t)$ and its complement. On $N(t)$, the pointwise contribution is at most $2e(x)$ whenever there is disagreement, by the threshold argument already established. This bounds the local part by the first term. Outside $N(t)$, a disagreement implies $e(x)\geq\Delta(x)/2$. Since $\Delta(x)>t$, for $q\geq1$, $\Delta(x)\leq 2^q e(x)^q/\Delta(x)^{q-1}\leq 2^q e(x)^q/t^{q-1}$. Thus the contribution outside $N(t)$ is bounded by the second term. Adding the two bounds proves the result. $\square$

This decomposition is a reminder that a boundary-localized analysis must account for the possibility of distant errors. The tail term can sometimes be made small using a suitable moment bound, or eliminated under a direct guarantee of correct decisions outside the neighborhood. The proposition itself does not assume a margin-distribution condition; it separates local estimation error from error away from the boundary.

Worked Example: Why Local Accuracy Alone Is Not Enough

Suppose $X$ is always equal to one point $b$, with $\eta(b)=0.90$ and $\hat\eta(b)=0.10$. Take $t=0.10$. The point is outside the boundary neighborhood because $\Delta(b)=|1.80-1|=0.80>t$. The local error in $N(t)$ is therefore zero.

Nevertheless, the Bayes classifier assigns label 1 and the plug-in classifier assigns label 0. The regret is $\Delta(b)=0.80$. Thus a claim that regret is controlled by boundary-neighborhood error alone would give zero here and would be false.

The local-plus-tail bound accounts for this case. With $q=1$, its local term is zero and its tail term is $2E[e\mathbf{1}\{X\notin N(t)\}]=2(0.80)=1.60$, which is loose but valid. The example shows why a fixed-neighborhood result needs an outside-agreement assumption, or a separate bound for errors outside the neighborhood.

Common Pitfall and Practical Use

Common mistake: “The regression estimate is very accurate near the Bayes boundary, so the classification regret must be small.” This reasoning ignores errors at feature values outside the chosen neighborhood. A sufficiently large error there can reverse a high-margin decision, as the last example demonstrates.

The correction is to state which kind of localization is being used. The self-localized inequality requires no separate outside-agreement assumption, but its relevant set depends on the pointwise estimation error. A fixed-neighborhood bound uses only error inside $N(t)$ if the plug-in classifier agrees with the Bayes rule outside $N(t)$. Otherwise, use a decomposition that also controls estimation error outside the neighborhood. These distinctions matter when translating regression guarantees into classification guarantees: the location of the error, not only its overall size, determines its relevance to regret.

Key takeaway: Plug-in regret is generated by disagreements and weighted by the margin gap. Errors near the Bayes boundary can be especially consequential, but local error bounds control total regret only when distant disagreements are ruled out or separately bounded.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

Why does disagreement between the Bayes and plug-in classifiers imply $\Delta(x)\leq2e(x)$?
In the fixed-neighborhood theorem, which assumption permits the regret outside $N(t)$ to be omitted?
If $P_X(N(t))=0.08$ and $t=0.05$, what is the first fixed-neighborhood upper bound on regret, assuming agreement outside $N(t)$?
Explain why a large regression error at a point need not create classification regret.
What additional term is needed when the classifier may disagree with the Bayes rule outside the chosen boundary neighborhood?