Smooth Decision Boundaries and Linear Margin Behavior

Why Boundary Geometry Determines Small Margins

In binary classification, observations near the Bayes decision boundary are the ones for which the conditional class probabilities are nearly tied. The probability of finding an observation this close to a tie matters for plug-in classification: it describes how much covariate probability lies in the region where small regression errors can change the predicted class.

When the regression function crosses the threshold smoothly, a margin band of width $t$ is a thin layer around a surface. Its probability is approximately its thickness multiplied by a weighted surface area. This gives a linear small-margin law, but the conclusion requires both a regular crossing and suitable behavior of the covariate distribution.

Definition: Let $Y\in\{0,1\}$, let $X\in\mathbb{R}^d$, and write $\eta(x)=P(Y=1\mid X=x)$ for a version of the regression function. The Bayes decision boundary is the threshold level set $S=\{x:\eta(x)=1/2\}$. The margin at $x$ is $M(x)=|2\eta(x)-1|$, and the small-margin probability at level $t\geq 0$ is $P(M(X)\leq t)$.

The factor of $2$ in this definition is a convention: $M(x)$ is the difference between the two conditional class probabilities, since $P(Y=1\mid X=x)-P(Y=0\mid X=x)=2\eta(x)-1$. Thus $M(x)\leq t$ is equivalent to $|\eta(x)-1/2|\leq t/2$. Keeping this conversion explicit prevents a factor-of-two error in the leading constant.

The Regular-Boundary Margin Law

Here is a precise form of the geometric argument. Let $X$ have a continuous density $p$ with compact support in $\mathbb{R}^d$. Suppose $\eta$ is continuously differentiable on an open neighborhood of that support. Assume that for some $\varepsilon>0$, the gradient $\nabla\eta(x)$ is nonzero at every point in the support of $p$ with $|\eta(x)-1/2|\leq\varepsilon$. This is the regular-crossing condition: locally, the threshold level set is a smooth $(d-1)$-dimensional surface rather than a tangency or flat region. Write $\mathcal{H}^{d-1}$ for surface area measure.

Theorem: Under these assumptions, define $$ C=\int_{S}\frac{p(x)}{\|\nabla\eta(x)\|}\,d\mathcal{H}^{d-1}(x). $$ As $t\downarrow 0$, $$ P(M(X)\leq t)=Ct+o(t). $$ If $C>0$, this means that $P(M(X)\leq t)/t\to C$; in particular, for all sufficiently small positive $t$, the small-margin probability is bounded above and below by positive constants times $t$.

The coefficient has two ingredients. The density $p(x)$ weights portions of the boundary where covariate observations are more common. The factor $1/\|\nabla\eta(x)\|$ is larger where the regression function crosses the threshold more slowly: for a fixed change in $\eta$, the corresponding band extends farther in the direction normal to the boundary.

Derivation of the Small-Margin Asymptotic

For $u$ near $1/2$, define the density of regression-function levels by the surface integral $$ g(u)=\int_{\{x:\eta(x)=u\}}\frac{p(x)}{\|\nabla\eta(x)\|}\,d\mathcal{H}^{d-1}(x). $$ The change of variables associated with the level sets of a continuously differentiable function gives $$ P(M(X)\leq t)=\int_{1/2-t/2}^{1/2+t/2}g(u)\,du $$ for sufficiently small $t$. To see why this change of variables has the displayed surface factor, consider local coordinates $(z,u)$ with $\eta(x)=u$, where $z$ parameterizes a level surface. The $z$-directions are tangent to the level surface and hence orthogonal to $\nabla\eta$. Differentiating $\eta(x)=u$ in the $u$-direction shows that the normal component of the coordinate derivative has length $1/\|\nabla\eta(x)\|$. The ordinary change-of-variables formula therefore gives volume element $d\mathcal{H}^{d-1}(x)\,du/\|\nabla\eta(x)\|$. A finite collection of such local coordinate neighborhoods covers the compact part of the support in the band, so the formula applies to the whole integral.

The same coordinates show that $g(u)$ is continuous at $1/2$. More explicitly, localize the integrals to finitely many coordinate neighborhoods with continuous weights summing to one. In each neighborhood the surface integral is an integral over $z$ of a continuous function of $(z,u)$, with the localized integrand supported in a bounded coordinate region. The integrands are bounded there and converge pointwise as $u\to 1/2$. Dominated convergence gives continuity for each localized integral, and their finite sum is continuous. Consequently, $g(1/2)=C$.

Convert margin to threshold distance.
$M(X)\leq t$ is precisely $\eta(X)\in[1/2-t/2,1/2+t/2]$.

Integrate over level surfaces.
The level-set change of variables expresses the probability as $\int_{1/2-t/2}^{1/2+t/2}g(u)\,du$.

Use continuity at the boundary level.
Since $g(u)\to g(1/2)=C$, the integral over an interval of length $t$ equals $Ct+o(t)$.

For completeness, the final approximation follows directly from continuity. Given any $\delta>0$, choose a neighborhood of $1/2$ where $|g(u)-C|<\delta$. For sufficiently small $t$, the whole integration interval is in that neighborhood, so $$ \left|\int_{1/2-t/2}^{1/2+t/2}g(u)\,du-Ct\right| \leq \int_{1/2-t/2}^{1/2+t/2}|g(u)-C|\,du \leq \delta t. $$ Since $\delta$ is arbitrary, the difference is $o(t)$, proving the theorem. $\square$

Worked Examples

Worked Example: A Straight Boundary Under a Uniform Distribution

Let $X=(X_1,X_2)$ be uniform on the unit square, and set $\eta(x)=0.2+0.6x_1$. Find the small-margin probability for $0\leq t\leq 0.6$, and identify its linear coefficient.

The boundary is $0.2+0.6x_1=0.5$, so $x_1=0.5$. The margin is $$ M(x)=|2\eta(x)-1|=|0.4+1.2x_1-1|=1.2|x_1-0.5|. $$ Thus $M(X)\leq t$ exactly when $|X_1-0.5|\leq t/1.2$. For $t\leq 0.6$, this interval stays within $[0,1]$, and its length is $2t/1.2=5t/3$. Since $X_1$ is uniform on $[0,1]$, $$ P(M(X)\leq t)=\frac{5}{3}t. $$ As a surface check, the boundary segment has length $1$, the density is $1$, and $\|\nabla\eta\|=0.6$. Hence $C=1/0.6=5/3$, matching the direct calculation.

Worked Example: A Curved Boundary with the Same Crossing Rate

Let $X=(X_1,X_2)$ be uniform on the unit square, let $h(y)=0.3+0.2\sin(2\pi y)$, and set $\eta(x_1,x_2)=0.5+0.4(x_1-h(x_2))$. Compute the margin probability for $0\leq t\leq 0.08$.

Here $h(y)$ lies between $0.1$ and $0.5$. The margin condition is $$ |2\eta(X)-1|=0.8|X_1-h(X_2)|\leq t, $$ or $|X_1-h(X_2)|\leq t/0.8$. When $t\leq0.08$, the half-width $t/0.8$ is at most $0.1$, so for every $X_2=y$ the interval around $h(y)$ remains inside $[0,1]$. Its length is $2t/0.8=2.5t$. Integrating over $y\in[0,1]$, whose density is $1$, gives $$ P(M(X)\leq t)=\int_0^1 2.5t\,dy=2.5t. $$ The surface calculation agrees. The boundary is $(h(y),y)$, with arc-length element $\sqrt{1+h'(y)^2}\,dy$, while $\|\nabla\eta\|=0.4\sqrt{1+h'(y)^2}$. Their ratio is $1/0.4=2.5$ at every $y$. Curvature changes the boundary’s length locally, but here the same factor appears in the gradient norm and cancels.

Worked Example: Boundary Mass Breaks the Linear Law

Keep $\eta(x)=0.2+0.6x$ on $[0,1]$, but let $X$ have probability $0.2$ at $x=0.5$ and probability $0.8$ distributed uniformly on $[0,1]$. What happens to $P(M(X)\leq t)$ as $t\downarrow0$?

The boundary is still $x=0.5$, and $M(x)=1.2|x-0.5|$. The atom at the boundary has margin zero, so it contributes $0.2$ to $P(M(X)\leq t)$ for every $t\geq0$. For $0\leq t\leq0.6$, the continuous uniform component contributes $0.8$ times an interval probability of $5t/3$. Therefore $$ P(M(X)\leq t)=0.2+0.8\left(\frac{5t}{3}\right) =0.2+\frac{4t}{3}. $$ The probability does not shrink to zero with the band width. The regression function has a nonzero gradient, but the covariate distribution has an atom on the boundary, so the density-based regular-boundary theorem does not apply.

What the Linear Law Does—and Does Not—Say

The theorem explains a common margin behavior under regular geometry: a band of threshold values of width $t$ corresponds to a spatial layer whose probability is of order $t$. The constant is not universal. It depends on how much covariate density lies along the boundary and on how steeply the regression function crosses the threshold there. A large gradient makes the layer thinner; high density or a large boundary contribution makes its probability greater.

A frequent mistake is to say that smoothness by itself guarantees the linear law. Smoothness makes the local geometric calculation possible, but a zero gradient at the threshold does not give the regular crossing used here. Nor does a smooth crossing rule out atoms in the distribution of $X$. Both the nonzero-gradient condition and the density assumption have work to do.

Another common error is to switch between $|\eta(X)-1/2|$ and $M(X)=|2\eta(X)-1|$ without adjusting the band width. For the former quantity, the interval of regression-function levels has total width $2t$ when its threshold is $t$; for the latter, it has total width $t$. The linear exponent is unchanged, but the coefficient changes. When applying a margin condition or comparing constants, first write the event as an interval for $\eta(X)$.

Key takeaway: At a regular decision boundary with a continuous covariate density, the probability of margin at most $t$ is $Ct+o(t)$. The coefficient is the boundary integral of density divided by the gradient magnitude; regular geometry alone is not enough if the covariate distribution places mass directly on the boundary.

Check Your Understanding

Use the definitions and derivation above to answer these questions.

Why does $M(X)\leq t$ correspond to a regression-function interval of width $t$, rather than $2t$?
For $\eta(x)=0.1+0.8x$ and $X$ uniform on $[0,1]$, find $P(M(X)\leq t)$ for sufficiently small $t$.
In the boundary integral, what does the factor $1/\|\nabla\eta(x)\|$ represent geometrically?
Which assumption fails when the covariate distribution has an atom on the decision boundary, and how does that change the small-margin probability?
Suppose the coefficient $C$ in the theorem is zero. Does the theorem then guarantee a positive linear lower bound? Explain.