Slow Rates When the Margin Condition Is Absent

Why Near-Ties Matter

In binary classification, the difficult observations are those for which the two labels have nearly equal conditional probability. A small error in estimating those probabilities can reverse the predicted label. The resulting excess risk is weighted by how close the observation was to a tie: reversing a decision near a tie costs little, while reversing one far from a tie costs more.

A margin condition quantifies how much probability can lie near a tie. When it holds with a positive exponent, it can turn a regression-estimation error into a faster classification excess-risk bound. When no positive exponent is available, that power improvement cannot be guaranteed. This does not mean every such distribution is hard to learn; it means near-tie probability alone no longer supplies a uniform fast-rate guarantee.

Margin and the Noise Condition

Let $X$ be a feature vector and $Y\in\{0,1\}$ a label. Write $\eta(x)=P(Y=1\mid X=x)$, using a measurable version of the conditional probability. A Bayes classifier predicts the more probable label: $g^*(x)=1$ when $\eta(x)>1/2$, and $g^*(x)=0$ when $\eta(x)<1/2$. Either prediction is Bayes-optimal when $\eta(x)=1/2$.

Definition: The margin is the random variable $\Delta(X)=|2\eta(X)-1|$, which takes values in $[0,1]$. A distribution satisfies a margin condition with exponent $\alpha>0$ and constant $C<\infty$ if $P(\Delta(X)\le t)\le Ct^\alpha$ for every $0<t\le1$. Absence of a positive margin exponent means that no such pair $(C,\alpha)$ works over this range.

The condition restricts the probability of observations whose conditional label probabilities are close. A larger $\alpha$ means that probability becomes small more rapidly as $t$ decreases. The statement that there is no positive exponent is not the same as saying that $P(\Delta=0)>0$: the probability can accumulate near zero without any exact ties.

How the Margin Enters Excess Risk

For a classifier $g$, let $R(g)=P(g(X)\ne Y)$ be its risk. Its excess risk is $R(g)-R(g^*)$. The following identity makes the role of the margin explicit.

Result: For any measurable binary classifier $g$, $$ R(g)-R(g^*)=E\!\left[\Delta(X)\mathbf{1}\{g(X)\ne g^*(X)\}\right]. $$

To verify the identity, condition on $X=x$. Predicting 0 has conditional error probability $\eta(x)$, while predicting 1 has conditional error probability $1-\eta(x)$. If $g(x)=g^*(x)$, the conditional excess risk is zero. If they disagree and $\eta(x)>1/2$, the conditional excess is $\eta(x)-(1-\eta(x))=2\eta(x)-1$. If they disagree and $\eta(x)<1/2$, it is $(1-\eta(x))-\eta(x)=1-2\eta(x)$. Both cases equal $\Delta(x)$. At a tie, both decisions have the same conditional risk and $\Delta(x)=0$. Taking expectation proves the identity.

Theorem: Suppose an estimated regression function $\widehat\eta$ satisfies $\sup_x|\widehat\eta(x)-\eta(x)|\le r$, and define $\widehat g(x)=1$ when $\widehat\eta(x)>1/2$, with either fixed convention at equality. Then $$ R(\widehat g)-R(g^*)\le 2r. $$ If the margin condition holds with exponent $\alpha>0$ and constant $C$, then the sharper bound $$ R(\widehat g)-R(g^*)\le C(2r)^{1+\alpha} $$ holds whenever $2r\le1$.

For the proof, at any $x$ where $\widehat g(x)\ne g^*(x)$, the two regression values must lie on opposite sides of $1/2$, allowing equality under the threshold convention. Thus $|\eta(x)-1/2|\le|\eta(x)-\widehat\eta(x)|\le r$, so $\Delta(x)\le2r$. The excess-risk identity therefore gives $$ R(\widehat g)-R(g^*)\le E[\Delta(X)\mathbf{1}\{\Delta(X)\le2r\}]\le2r. $$ Under the margin condition, the same expectation is at most $2r\,P(\Delta(X)\le2r)$, which is at most $2r\,C(2r)^\alpha=C(2r)^{1+\alpha}$. This proves both bounds. $\square$

The distinction is in the last step: a positive exponent turns the probability of an ambiguous region into an extra power of $r$. Without such a condition, the argument gives the general $2r$ bound but does not justify a faster power. For example, if regression estimation has error of order $n^{-\beta/(2\beta+d)}$ under suitable smoothness and design assumptions, this calculation gives that same order as a general excess-risk bound. A positive margin exponent can improve it; without one, that improvement is not guaranteed.

Worked Examples of Missing Margin Decay

Worked Example: Exact Ties With Positive Probability

Suppose $X$ has two possible values, $a$ and $b$, with $P(X=a)=1/4$ and $P(X=b)=3/4$. Let $\eta(a)=1/2$ and $\eta(b)=3/4$. At $a$, $\Delta(a)=0$; at $b$, $\Delta(b)=|3/2-1|=1/2$.

For every $t$ with $0<t<1/2$, $P(\Delta\le t)=1/4$. If a margin condition held for some $\alpha>0$ and finite $C$, it would require $1/4\le Ct^\alpha$ for every such $t$. But $Ct^\alpha$ tends to zero as $t$ tends to zero, a contradiction. Thus no positive exponent works.

The mass at the exact tie does not itself create excess risk: either label is optimal at $a$. This example shows that ties violate the margin condition, not that mistakes on ties are costly.

Worked Example: Near-Ties Without Any Atom at the Boundary

Let $X$ take values $j=1,2,\ldots$, with $P(X=j)=p_j=1/[j(j+1)]$, and define $\eta(j)=(1+e^{-j})/2$. The probabilities sum to one because $1/[j(j+1)]=1/j-1/(j+1)$. Here $\Delta(j)=e^{-j}>0$ for every $j$, so there is no mass at an exact tie.

At $t=e^{-J}$, where $J$ is a positive integer, the event $\Delta\le t$ is $X\ge J$. The telescoping sum gives $$ P(\Delta\le e^{-J})=\sum_{j=J}^{\infty}\frac{1}{j(j+1)}=\frac{1}{J}. $$ If a margin condition with exponent $\alpha>0$ held, then $1/J\le C e^{-\alpha J}$ for every $J$. Equivalently, $e^{\alpha J}/J\le C$, which is impossible because $e^{\alpha J}/J$ grows without bound. Hence the margin probability approaches zero, but more slowly than every positive power of $t$.

The same model displays the corresponding scale of near-tie risk. Consider a perturbed regression function that equals $(1-e^{-j})/2$ for $j\ge J$ and equals $\eta(j)$ otherwise. Its uniform error is at most $e^{-J}$, and its threshold classifier reverses the Bayes decision precisely for $j\ge J$. The excess risk is $$ \sum_{j=J}^{\infty}\frac{e^{-j}}{j(j+1)}. $$ The first term is $e^{-J}/[J(J+1)]$. For an upper bound, $1/[j(j+1)]\le1/J^2$ when $j\ge J$, so the sum is at most $e^{-J}/[J^2(1-e^{-1})]$. Thus the excess is bounded above and below by constant multiples of $e^{-J}/J^2$. Along these scales it is of order $t/[\log(1/t)]^2$, not of order $t^{1+\alpha}$ for any fixed $\alpha>0$. This is a particular perturbation calculation, not a claim that every learning procedure has this risk.

Worked Example: Testing Two Nearly Indistinguishable Label Laws

Let $X$ be constant, so classification reduces to predicting the more probable label. Compare two distributions: under $P_+$, $Y$ is Bernoulli with probability $1/2+\delta$, and under $P_-$, it is Bernoulli with probability $1/2-\delta$, where $\delta=1/(16\sqrt n)$. The Bayes labels differ, and a wrong prediction has excess risk $2\delta$ under either distribution.

For one observation, the Kullback–Leibler divergence is $$ \operatorname{KL}(P_+,P_-)=2\delta\log\!\left(\frac{1+2\delta}{1-2\delta}\right)\le16\delta^2. $$ For the inequality, put $x=2\delta\le1/2$. The derivative of $\log((1+x)/(1-x))$ is $2/(1-x^2)\le 8/3<4$ on this interval, and the logarithm is zero at zero. Hence the logarithm is at most $4x=8\delta$, giving the stated bound. For $n$ independent observations the divergence is at most $16n\delta^2=1/16$.

Pinsker's inequality gives total variation distance between the two sample distributions at most $\sqrt{(1/16)/2}=1/\sqrt{32}$. Any decision rule for choosing between the two Bayes labels therefore has average error probability at least $(1-1/\sqrt{32})/2$. Its average excess risk is at least $$ 2\delta\frac{1-1/\sqrt{32}}{2} =\delta(1-1/\sqrt{32}), $$ which is a positive constant times $n^{-1/2}$. Even this simple pair prevents a uniform improvement over the $n^{-1/2}$ scale when the separation is allowed to shrink with sample size. Each fixed pair has a positive margin gap; the point is that the constants in its margin bounds are not uniform as $\delta$ shrinks. A uniform fast-rate claim needs uniform control, not just a condition that can hold separately with changing constants.

What Absence of a Margin Exponent Does—and Does Not—Say

The examples separate three ideas. A positive probability of exact ties rules out every positive margin exponent, though decisions at those ties incur no excess risk. A distribution can also have no exact ties and still place probability near zero too slowly for any power condition. Finally, weakly separated labels can be hard to distinguish from finite data, as the two-point calculation shows.

Absence of a positive exponent is not, by itself, a theorem that every classifier converges slowly or that every distribution is difficult. The distribution in the near-tie example has a simple structure, and a learner that knows that structure can exploit it. Rates also depend on assumptions controlling the regression function, the feature distribution, and the available model class. The margin condition supplies one specific ingredient: a bound on how much probability is concentrated near ambiguous decisions.

A common mistake is to insert a positive exponent into a fast-rate formula merely because $P(\Delta\le t)$ tends to zero as $t$ tends to zero. Convergence to zero alone is insufficient. The log-tail example has that convergence, but for every $\alpha>0$, the ratio $P(\Delta\le e^{-J})/(e^{-J})^\alpha=e^{\alpha J}/J$ is unbounded. The correction is to verify the required power inequality, including a fixed finite constant over the stated range, before claiming the corresponding rate improvement.

Key takeaway: Without a uniform positive margin exponent, near-tie probability may decay too slowly to yield a power improvement in excess risk. Use the general bound supported by the other assumptions, and treat faster rates as requiring additional verified control of the margin distribution.

Check Your Understanding

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

Why does a positive mass at $\Delta=0$ violate every positive-exponent margin condition?
In the discrete near-tie example, calculate $P(\Delta\le e^{-J})$ and explain why it cannot be bounded by $Ce^{-\alpha J}$ for any fixed $\alpha>0$.
Why does the excess-risk identity assign zero cost to a disagreement at an exact tie?
What additional inequality does a positive margin exponent provide in the proof of the plug-in excess-risk bound?
In the two-point example, why does choosing $\delta$ as a function of $n$ illustrate the need for uniform margin constants?