Worked Examples of Boundary Geometry and Regret

Boundary Shape, Margin Probability, and Regret

A plug-in classifier estimates the regression function $\eta(x)=P(Y=1\mid X=x)$ and assigns class 1 when its estimate is at least $1/2$. Its errors matter most near points where $\eta(x)=1/2$: there the two classes are nearly equally likely, so a small estimation error can change the chosen class. But the effect also depends on how much probability mass lies near those points. The examples below calculate that mass and its contribution to regret for regular, flat, and multiple piecewise-linear boundaries.

Let $X$ take values in $[0,1]$, and suppose $Y\in\{0,1\}$. Write $\eta(x)=P(Y=1\mid X=x)$. The Bayes classifier assigns class 1 when $\eta(x)\ge 1/2$, and class 0 otherwise. Define the margin variable $\Delta(X)=|2\eta(X)-1|$. It measures how far the conditional class probabilities are from a tie; in particular, $\Delta=0$ at a decision boundary.

Definition: The margin probability at scale $t>0$ is $M(t)=P(0<\Delta(X)\le t)$. It counts probability mass close to a decision boundary, excluding points exactly tied, which contribute no classification regret. The weighted margin integral is $W(u)=E[\Delta(X)\mathbf{1}\{0<\Delta(X)\le u\}]$.

The factor of 2 in $\Delta$ is deliberate: a regression error of size $\varepsilon$ can change the sign of $2\eta-1$ only when $\Delta\le 2\varepsilon$. The probability $M(t)$ describes how frequently such vulnerable points occur; $W(t)$ additionally weights them by the cost of choosing the wrong class.

Two Risk Facts for Plug-In Rules

For a classifier $g:[0,1]\to\{0,1\}$, define its risk as $R(g)=P(g(X)\ne Y)$. Conditional on $X=x$, predicting 0 has error probability $\eta(x)$, while predicting 1 has error probability $1-\eta(x)$. The smaller of these is achieved by the Bayes classifier.

Theorem: For every measurable classifier $g$, its excess risk over the Bayes classifier $g^*$ is $$ R(g)-R(g^*)=E\!\left[\Delta(X)\mathbf{1}\{g(X)\ne g^*(X)\}\right]. $$ If a measurable estimate $\hat\eta$ satisfies $|\hat\eta(X)-\eta(X)|\le\varepsilon$ almost surely, then the plug-in classifier $\hat g=\mathbf{1}\{\hat\eta(X)\ge 1/2\}$ satisfies $$ R(\hat g)-R(g^*)\le W(2\varepsilon). $$

Proof. At a fixed $x$, the conditional error of predicting 1 is $1-\eta(x)$, and that of predicting 0 is $\eta(x)$. If $g(x)=g^*(x)$, their difference is zero. If the predictions differ, the excess conditional error is $|(1-\eta(x))-\eta(x)|=|1-2\eta(x)|=\Delta(x)$. Averaging over $X$ proves the identity.

For the plug-in bound, suppose $\eta(x)>1/2$, so the Bayes prediction is 1. If $\hat g(x)=0$, then $\hat\eta(x)<1/2$, and therefore $|\eta(x)-\hat\eta(x)|>\eta(x)-1/2$. The assumed error bound implies $\eta(x)-1/2<\varepsilon$, hence $\Delta(x)<2\varepsilon$. If $\eta(x)<1/2$ and $\hat g(x)=1$, the same reasoning gives $1/2-\eta(x)\le\varepsilon$, hence $\Delta(x)\le2\varepsilon$. At $\eta(x)=1/2$, the regret contribution is zero. Thus disagreement contributes only where $0<\Delta(x)\le2\varepsilon$. Applying the identity and dropping the disagreement indicator gives the stated bound. $\square$

A useful consequence is that if, for some constants $C>0$, $\alpha>0$, and $t_0>0$, the margin condition $M(t)\le Ct^\alpha$ holds for $0<t\le t_0$, then for $2\varepsilon\le t_0$, $$ R(\hat g)-R(g^*)\le W(2\varepsilon)\le 2\varepsilon\,M(2\varepsilon)\le C(2\varepsilon)^{\alpha+1}. $$ The middle inequality follows because every $\Delta$ counted by $W(2\varepsilon)$ is at most $2\varepsilon$. The examples show how boundary geometry determines $\alpha$, and why this bound can be conservative for a particular perturbation.

Worked Examples of Boundary Geometry

Worked Example: A Regular Linear Crossing

Let $X$ be uniform on $[0,1]$ and let $\eta(x)=1/2+(x-1/2)/2$. This is a valid regression function: it ranges from $1/4$ to $3/4$. Its decision boundary is $x=1/2$, and $\Delta(x)=|2\eta(x)-1|=|x-1/2|$.

For $0<t\le1/2$, the event $0<\Delta(X)\le t$ consists of two intervals, each of length $t$, one on either side of $1/2$. Uniformity gives $$ M(t)=2t. $$ For $0<u\le1/2$, integrating the margin over those same two intervals gives $$ W(u)=2\int_0^u z\,dz=u^2. $$

Now take the perturbed estimate $\hat\eta(x)=\eta(x)-\varepsilon$, with $0<\varepsilon\le1/4$. Its uniform error is exactly $\varepsilon$. It changes the prediction only on the class-1 side where $\eta(x)\ge1/2$ but $\hat\eta(x)<1/2$. Writing $z=x-1/2$, this means $0\le z<2\varepsilon$. The actual regret is therefore $$ R(\hat g)-R(g^*)=\int_0^{2\varepsilon}z\,dz=2\varepsilon^2. $$ The general bound gives $W(2\varepsilon)=(2\varepsilon)^2=4\varepsilon^2$. Both calculations show quadratic regret here; the general bound is valid but not exact for this one-sided perturbation.

Worked Example: A Flat Cubic Crossing

Keep $X$ uniform on $[0,1]$, but set $\eta(x)=1/2+(x-1/2)^3/2$. The function ranges from $7/16$ to $9/16$, so it is a valid regression function. It crosses $1/2$ at $x=1/2$, but does so flatly: $\Delta(x)=|x-1/2|^3$.

For $0<t\le1/8$, the margin condition $\Delta\le t$ is equivalent to $|x-1/2|\le t^{1/3}$. The interval has length $2t^{1/3}$, giving $$ M(t)=2t^{1/3}. $$ For $0<u\le1/8$, set $r=u^{1/3}$. The two sides of the boundary contribute equally, so $$ W(u)=2\int_0^r z^3\,dz=\frac{r^4}{2}=\frac{u^{4/3}}{2}. $$ The margin probability grows as $t^{1/3}$, not linearly: a flat crossing keeps $\Delta$ small over a wider region.

For the estimate $\hat\eta=\eta-\varepsilon$, where $0<\varepsilon\le1/16$, the class-1 predictions are incorrectly changed to class 0 when $0<x-1/2<(2\varepsilon)^{1/3}$. The condition $\varepsilon\le1/16$ ensures this interval stays within $[1/2,1]$. Direct integration gives $$ R(\hat g)-R(g^*)=\int_0^{(2\varepsilon)^{1/3}}z^3\,dz =\frac{(2\varepsilon)^{4/3}}{4}. $$ The general bound is $W(2\varepsilon)=(2\varepsilon)^{4/3}/2$. The slower power $4/3$, compared with the regular crossing’s power 2, reflects the greater mass near this flat boundary.

Worked Example: Two Piecewise-Linear Boundaries

Let $X$ again be uniform on $[0,1]$, and define $g(x)=2\eta(x)-1$ by $$ g(x)= \begin{cases} x-\frac14, & 0\le x\le\frac12,\\ \frac34-x, & \frac12<x\le1. \end{cases} $$ Set $\eta(x)=(1+g(x))/2$. The function $g$ ranges from $-1/4$ to $1/4$, so $\eta$ ranges from $3/8$ to $5/8$. There are two decision boundaries, at $1/4$ and $3/4$, and $\Delta(x)=|g(x)|$.

For $0<t\le1/4$, each boundary has a length-$t$ neighborhood on both sides where $\Delta\le t$. The four pieces are disjoint except for endpoints, which have probability zero. Thus $$ M(t)=4t,\qquad W(u)=4\int_0^u z\,dz=2u^2\quad(0<u\le1/4). $$ Compared with a single regular crossing, the two boundaries double the amount of near-boundary mass.

Now use $\hat\eta=\eta-\varepsilon$, with $0<\varepsilon\le1/8$, and put $u=2\varepsilon\le1/4$. This perturbation can change class 1 to class 0 only where $g>0$ and $g<2\varepsilon=u$. The positive region has two branches, one next to each boundary. On each branch $g$ rises linearly from zero, so the regret is $$ R(\hat g)-R(g^*)=2\int_0^u z\,dz=u^2=4\varepsilon^2. $$ The general bound is $W(u)=2u^2=8\varepsilon^2$. The direct calculation accounts for the two positive branches; the margin bound also includes near-boundary mass on the negative branches, where this particular downward perturbation causes no errors.

How to Read the Calculations

The examples separate two ingredients. The shape of $\Delta(x)$ near a boundary determines how quickly $M(t)$ grows as $t$ increases. The number of boundary neighborhoods and the distribution of $X$ determine how much probability mass they contain. For a regular crossing under a uniform design, $M(t)$ is proportional to $t$. A cubic crossing gives $M(t)$ proportional to $t^{1/3}$. Multiple regular crossings add their local contributions.

The weighted integral $W(u)$ then describes a worst-case regret contribution from all points with margin at most $u$. It can exceed the regret of a particular estimator: the uniform-error argument does not specify which vulnerable points the estimator actually misclassifies. That is why the exact shifted-estimator calculations above can be smaller than $W(2\varepsilon)$.

Common mistake: It is tempting to infer regret from the number of boundary points alone, or to treat all near-boundary points as equally costly. Neither is sufficient. The margin probability depends on the design distribution as well as the regression function, and regret weights each point by $\Delta$. Compute both $M(t)$ and $W(t)$, and distinguish the general plug-in bound from the exact regret of a specified perturbation.

Key takeaway: For a plug-in classifier with uniform regression error at most $\varepsilon$, only points with margin at most $2\varepsilon$ can be misclassified. Boundary geometry and probability mass determine how much regret those points can contribute.

Check Your Understanding

Use the definitions and calculations in this tutorial to answer the following questions.

For the regular linear crossing, why does $M(t)$ have two contributions of length $t$?
For the cubic crossing, solve $|x-1/2|^3\le t$ for the width of the corresponding interval.
In the piecewise-linear example, why does the margin probability include four near-boundary pieces?
Explain why the plug-in disagreement condition uses $2\varepsilon$ when the regression estimate has error at most $\varepsilon$.
Why can the weighted margin bound be larger than the exact regret for a downward-shifted estimate?

Worked Examples of Boundary Geometry and Regret

What You'll Learn