Effective Dimension of Decision Boundaries

Why Boundary Geometry Enters Classification Rates

In binary classification, errors are most consequential near locations where the two labels are nearly equally likely. The set separating the Bayes decisions helps identify where such locations occur, but its Euclidean dimension alone does not determine how much probability lies nearby. The distribution of the covariates matters too: a thin geometric neighborhood can contain substantial probability if the design distribution concentrates there.

A useful way to quantify the relevant geometry is to measure the probability mass in a shrinking neighborhood of the decision boundary. This effective dimension links boundary geometry to small-margin probabilities and to the excess risk of classifiers whose errors are localized near that boundary. It is a link under stated assumptions, not a universal conversion from Euclidean dimension to a learning rate.

Boundary Neighborhoods and Effective Dimension

Let $X$ take values in a subset of $\mathbb{R}^d$, and consider binary labels $Y\in\{0,1\}$. Write $\eta(x)=P(Y=1\mid X=x)$. A Bayes classifier predicts 1 when $\eta(x)>1/2$ and 0 when $\eta(x)<1/2$; either decision is optimal at a tie. Let $\Gamma$ be the decision boundary of interest, and define the distance $r(x)=\operatorname{dist}(x,\Gamma)$. For $h>0$, its $h$-neighborhood is $T_h(\Gamma)=\{x:r(x)\le h\}$.

Definition: The effective boundary dimension $q$ (more precisely, the effective tube-mass exponent) describes how covariate probability shrinks near $\Gamma$. We say the tube mass has exponent $q$ if there are constants $0<c\le C<\infty$ and $h_0>0$ such that $$ c h^q \le P_X(T_h(\Gamma)) \le C h^q,\qquad 0<h\le h_0. $$ Here $P_X$ is the distribution of $X$. The exponent concerns probability mass, not just the Euclidean dimension of $\Gamma$.

When $q>0$, the probability of lying exactly on the boundary is zero, since $P_X(\Gamma)\le P_X(T_h(\Gamma))\le Ch^q$ for every sufficiently small $h$, and the upper bound tends to zero. An exponent $q=0$ instead allows nonvanishing mass arbitrarily close to, or directly on, the boundary. The definition can also be applied with one-sided bounds when only an upper bound is available; that weaker condition does not establish a matching rate.

When Euclidean Geometry Predicts Tube Mass

There is a standard geometric setting in which Euclidean dimension does give the tube-mass exponent. Suppose $X$ has a density with respect to $d$-dimensional volume that is bounded above and bounded away from zero on a neighborhood of a compact, regular, embedded $s$-dimensional submanifold $\Gamma\subset\mathbb{R}^d$. Assume, for example, that $\Gamma$ is $C^2$ and has positive reach, so points sufficiently close to it have well-behaved normal coordinates. Then

P_X(T_h(\Gamma))\asymp h^{d-s},\qquad q=d-s.

The reason is that a small tube has $s$ directions along the manifold and $d-s$ normal directions. Its volume is of order $h^{d-s}$; the density bounds transfer that volume order to probability. In particular, a regular hypersurface in a full-dimensional design has $s=d-1$ and $q=1$. A lower-dimensional regular set has larger codimension, and therefore larger $q$, under these design and regularity assumptions. In general, $q$ depends on the distribution of $X$ as well as on the boundary.

Worked Example: A Hyperplane Under a Full-Dimensional Design

Let $X$ be uniform on $[0,1]^3$, and take $\Gamma=\{x:x_1=1/2\}\cap[0,1]^3$. For $0<h\le1/2$, its tube in the cube is the slab $1/2-h\le x_1\le1/2+h$. The other two coordinates range over intervals of length 1, so $$ P_X(T_h(\Gamma))=(2h)(1)(1)=2h. $$ Thus $q=1$. The boundary is two-dimensional in three-dimensional space, and the tube has one shrinking normal direction.

Worked Example: A Lower-Dimensional Boundary on a Lower-Dimensional Support

Let $X=(U,V,0)$, where $U$ and $V$ are independent uniform random variables on $[0,1]$. The covariate distribution lies on a plane in $\mathbb{R}^3$. Let the decision boundary on this support be the line $\Gamma=\{(1/2,v,0):0\le v\le1\}$, which separates the two halves of the support. For $0<h\le1/2$, distance to this line is $|U-1/2|$, so $$ P_X(T_h(\Gamma))=P(|U-1/2|\le h)=2h. $$ The effective exponent is $q=1$, the codimension of the line within the two-dimensional support. Although the line has codimension two in ambient $\mathbb{R}^3$, the ambient formula $d-s$ does not apply: $X$ has no three-dimensional density bounded below near the line. The distribution’s support determines which geometric directions carry probability.

From Tube Mass to Small-Margin Mass

The margin at $x$ is $\Delta(x)=|2\eta(x)-1|$. It measures the conditional advantage of the more likely label over the other one. To connect margin probabilities to boundary geometry, a further condition is needed: the margin must grow with distance from the boundary at a specified rate. For the following result, assume that, in a neighborhood of $\Gamma$, there are constants $a,b>0$ and $\kappa>0$ such that

a\,r(x)^\kappa\le \Delta(x)\le b\,r(x)^\kappa.

Assume also that every sufficiently small-margin point lies in this neighborhood. This excludes a separate region far from $\Gamma$ where $\Delta$ is arbitrarily close to zero. The exponent $\kappa$ describes how quickly the conditional label preference increases with distance; it is distinct from the tube-mass exponent $q$.

Theorem: Suppose $q>0$, the tube-mass bounds $c h^q\le P_X(T_h(\Gamma))\le C h^q$ hold for sufficiently small $h$, and the two-sided margin-distance condition above holds in a neighborhood containing all sufficiently small-margin points. Then, for all sufficiently small $t>0$, there are positive constants $c_1,C_1$ such that $$ c_1 t^{q/\kappa}\le P(\Delta(X)\le t)\le C_1 t^{q/\kappa}. $$

Proof. If $\Delta(x)\le t$, the lower margin-distance bound implies $a r(x)^\kappa\le t$, hence $r(x)\le(t/a)^{1/\kappa}$. Thus the small-margin event is contained in $T_{(t/a)^{1/\kappa}}(\Gamma)$, and its probability is at most $C(t/a)^{q/\kappa}$. Conversely, if $r(x)\le(t/b)^{1/\kappa}$, then the upper margin-distance bound gives $\Delta(x)\le b r(x)^\kappa\le t$. Therefore the tube $T_{(t/b)^{1/\kappa}}(\Gamma)$ is contained in the small-margin event, whose probability is at least $c(t/b)^{q/\kappa}$. Choosing $t$ small enough that both radii are within the range of the tube bounds proves the result. $\square$

Under these assumptions, the usual small-margin exponent is therefore $\alpha=q/\kappa$: the probability of a margin at most $t$ scales as $t^\alpha$. The geometry alone does not specify this exponent. It supplies $q$, while the way $\eta(x)$ approaches $1/2$ supplies $\kappa$.

Worked Example: Margin Exponent and Risk of a Shifted Boundary

Let $X$ be uniform on $[0,1]$, with boundary $\Gamma=\{1/2\}$. For a fixed $\kappa>0$, define $$ \eta(x)=\frac12+\frac14\,\operatorname{sign}(x-1/2)|x-1/2|^\kappa, $$ where the value at $x=1/2$ is $1/2$. Since $|x-1/2|\le1/2$, the added term has absolute value at most $1/4$, so $\eta(x)$ is a valid probability. Here $r(x)=|x-1/2|$, $\Delta(x)=\frac12r(x)^\kappa$, and $P_X(T_h(\Gamma))=2h$; hence $q=1$.

For $0<t\le \frac12(1/2)^\kappa$, the event $\Delta(X)\le t$ is exactly $r(X)\le(2t)^{1/\kappa}$. Its probability is $$ P(\Delta(X)\le t)=2(2t)^{1/\kappa}, $$ so the margin exponent is $1/\kappa=q/\kappa$.

Now move the classifier’s boundary to $1/2+h$, with $0<h\le1/2$. It disagrees with the Bayes classifier on $(1/2,1/2+h)$. The excess classification risk is the integral of $\Delta(x)$ over that interval: $$ \int_{1/2}^{1/2+h}\frac12(x-1/2)^\kappa\,dx =\frac12\int_0^h u^\kappa\,du =\frac{h^{\kappa+1}}{2(\kappa+1)}. $$ The disagreement region has probability $h$, while the excess risk is of order $h^{q+\kappa}=h^{\kappa+1}$. The extra factor reflects the small label margin near the boundary.

Boundary-Localized Excess Risk

The preceding calculation generalizes when both sides of the tube-mass scaling are available. For a classifier $g$, its excess risk over a Bayes classifier $g^*$ is $$ R(g)-R(g^*)=E\!\left[\Delta(X)\mathbf{1}\{g(X)\ne g^*(X)\}\right]. $$ This identity follows by conditioning on $X=x$: choosing the less likely label increases the conditional error probability by $|2\eta(x)-1|$. Consider errors confined to $T_h(\Gamma)$, and suppose $a r(x)^\kappa\le\Delta(x)\le b r(x)^\kappa$ there.

Derived rate: If $q>0$, the tube-mass bounds hold, and the classifier disagrees with the Bayes rule on a region $A_h\subseteq T_h(\Gamma)$, then $$ R(g)-R(g^*)\le b h^\kappa P_X(T_h(\Gamma))\le bC h^{q+\kappa}. $$ A matching lower bound requires enough disagreement probability at distances comparable to $h$; it does not follow just from $A_h\subseteq T_h(\Gamma)$.

For example, suppose $P_X(A_h)\ge c_0h^q$ and $A_h\subseteq\{x:ah\le r(x)\le h\}$ for a fixed $a>0$. Then $\Delta(x)\ge a_0(ah)^\kappa$ on $A_h$, where $a_0$ is the lower margin-distance constant. Consequently, $$ R(g)-R(g^*)\ge a_0a^\kappa h^\kappa P_X(A_h) \ge a_0a^\kappa c_0 h^{q+\kappa}. $$ Together the bounds give excess risk of order $h^{q+\kappa}$ for this type of boundary-localized error.

This calculation explains how effective dimension enters a rate argument: it determines the probability mass affected by a geometric displacement, and the margin determines the loss per affected point. Translating this relationship into a sample-size rate also requires assumptions about how accurately a method can locate or approximate the boundary. Tube geometry alone does not supply those assumptions or a minimax rate.

Distribution Can Override Euclidean Dimension

A lower-dimensional boundary does not automatically imply a larger effective exponent. Consider a design distribution that places positive probability directly on $\Gamma$. Its tube mass is at least that boundary probability for every $h>0$, so it cannot decay like $h^q$ for any $q>0$. For instance, if $X$ is uniform on the line segment $\Gamma=\{(u,0):0\le u\le1\}$ and $\eta(X)=1/2$ there, then $P_X(T_h(\Gamma))=1$ for every $h>0$. The tube-mass exponent is $q=0$, despite the segment’s Euclidean dimension. This example also has positive tie mass, so it does not satisfy a positive small-margin exponent for $P(\Delta\le t)$.

More generally, a design can concentrate near a boundary, avoid it, or live on a lower-dimensional support. Each possibility changes the probability of a tube. A geometric codimension calculation is justified only when the support and density assumptions needed for it are actually present.

Common Pitfall

Wrong reasoning: “The boundary has Euclidean dimension $s$ in $\mathbb{R}^d$, so its effective exponent is always $d-s$.” This silently assumes a full-dimensional design with suitable density and regularity.
Correction: First evaluate or bound $P_X(T_h(\Gamma))$. Only under conditions such as a density bounded above and below near a regular manifold can one conclude $q=d-s$. On a lower-dimensional support, use the geometry relative to that support when its design distribution permits it; with mass on the boundary, $q$ may be zero.
Another caution: A tube-mass exponent is not by itself a margin exponent or a sample-size rate. The margin-distance behavior and the statistical difficulty of estimating the boundary also matter.

Key takeaway: Effective boundary dimension is a probability-mass exponent. Under regular full-dimensional designs it equals geometric codimension, and, combined with a margin-distance exponent, it determines small-margin and boundary-localized excess-risk scaling. Without those assumptions, the covariate distribution can change the conclusion.

Check Your Understanding

Use the tube-mass definition and state any assumptions you need.

A regular hypersurface lies in $\mathbb{R}^5$, and the design density is bounded above and below near it. What is its tube-mass exponent?
If $P_X(T_h(\Gamma))\asymp h^q$ and $\Delta(x)\asymp r(x)^\kappa$ near the boundary, what small-margin exponent follows?
Why can a set of low Euclidean dimension have effective exponent zero?
For errors confined to a tube of width $h$, explain why the excess-risk upper bound has order $h^{q+\kappa}$ under the stated margin and tube assumptions.
What additional assumption is needed before the ambient formula $q=d-s$ can be used?