Plug-In Rates When the Margin Condition Is Weak

Why the Margin Exponent Changes the Rate

A plug-in classifier estimates the binary regression function and assigns a label according to whether the estimate lies above or below the Bayes threshold. Its classification regret depends not only on how accurately the regression function is estimated, but also on how much probability lies near that threshold. If many observations have regression values close to one half, a small estimation error can change many labels. A margin condition quantifies this boundary mass.

The focus here is the comparison across margin exponents. A larger exponent means that the probability of being close to the threshold must decrease more rapidly as the neighborhood narrows. Exponent zero imposes no such decay, so it produces a weaker regret guarantee.

Margin Conditions and Plug-In Regret

Let $X$ be a feature vector and $Y\in\{0,1\}$ a label. Write $\eta(x)=P(Y=1\mid X=x)$, and let $\hat\eta$ be a measurable estimate of $\eta$. The plug-in classifier is $\hat g(x)=\mathbf{1}\{\hat\eta(x)\ge 1/2\}$, while a Bayes classifier is $g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$. Define the margin variable $\Delta(X)=|2\eta(X)-1|$, which lies in $[0,1]$.

Definition: For $\alpha\ge 0$ and $C\ge 1$, the distribution satisfies a margin condition with exponent $\alpha$ and constant $C$ if $$ P(\Delta(X)\le t)\le C t^\alpha,\qquad 0<t\le 1. $$ The $L_p$ regression error is $R_p=(E[|\hat\eta(X)-\eta(X)|^p])^{1/p}$, when this moment is finite.

At $\alpha=0$, $t^\alpha=1$, so the condition says only $P(\Delta\le t)\le C$. With $C\ge1$, this is true for every distribution and every $t$. It supplies no useful decay as $t$ approaches zero and allows positive probability exactly at the boundary $\Delta=0$. By contrast, any condition with $\alpha>0$ implies $P(\Delta=0)=0$: the events $\{\Delta\le t\}$ decrease to $\{\Delta=0\}$ as $t\downarrow0$, while their probabilities are bounded by $Ct^\alpha$, which tends to zero.

For a fixed classifier $g$, its excess classification risk over the Bayes rule is $E[\Delta(X)\mathbf{1}\{g(X)\ne g^*(X)\}]$. This follows by comparing the two conditional error probabilities at each $x$: choosing the less likely label instead of the more likely one increases conditional error by $|2\eta(x)-1|$. In particular, this identity describes the regret of $\hat g$.

A Threshold-Splitting Bound

Choose a threshold $t$ between zero and one. Points with $\Delta\le t$ are close to the decision boundary and are controlled by the margin condition. On points with $\Delta>t$, disagreement requires a sufficiently large regression estimation error.

Theorem: Suppose the margin condition with exponent $\alpha\ge0$ and constant $C\ge1$ holds, and $R_p<\infty$ for some $p\ge1$. For every $0<t\le1$, the plug-in regret satisfies $$ E[\Delta(X)\mathbf{1}\{\hat g(X)\ne g^*(X)\}] \le C t^{\alpha+1}+2^p R_p^p t^{-(p-1)}. $$

Proof. Split the regret according to whether $\Delta\le t$ or $\Delta>t$. The first part is at most $$ E[\Delta\mathbf{1}\{\Delta\le t\}]\le tP(\Delta\le t)\le C t^{\alpha+1}. $$ For the second part, whenever $\Delta>0$ and the two classifiers disagree, $|\hat\eta(X)-\eta(X)|\ge\Delta(X)/2$. This holds whether $\eta(X)$ is above or below one half: crossing the threshold requires an error at least as large as the distance from $\eta(X)$ to that threshold. Thus, on $\{\Delta>t,\hat g\ne g^*\}$, $$ \Delta\le 2^p|\hat\eta-\eta|^p\Delta^{1-p} \le 2^p t^{1-p}|\hat\eta-\eta|^p. $$ The last inequality uses $p\ge1$ and $\Delta>t$. Taking expectations bounds the second part by $2^p R_p^p t^{-(p-1)}$. Adding the two parts proves the result. $\square$

This bound makes the role of the margin exponent explicit: the near-boundary contribution is $Ct^{\alpha+1}$. The other term penalizes choosing a threshold that is too small, because errors farther from the boundary then require a more demanding regression deviation.

Converting Regression Error into a Regret Rate

Theorem: Under the assumptions above, for $p>1$ there is a finite constant $K$, depending only on $C,\alpha,p$, such that $$ E[\Delta(X)\mathbf{1}\{\hat g(X)\ne g^*(X)\}] \le K R_p^{\,p(\alpha+1)/(\alpha+p)}. $$ If $p=1$, the regret is at most $2R_1$.

Proof for $p>1$. First suppose $R_p>0$. The threshold bound has the form $C t^{\alpha+1}+B t^{-(p-1)}$, where $B=2^pR_p^p$. Its derivative for $t>0$ is $$ C(\alpha+1)t^\alpha-B(p-1)t^{-p}. $$ The derivative is zero at $$ t_0=\left(\frac{2^pR_p^p(p-1)}{C(\alpha+1)}\right)^{1/(\alpha+p)}. $$ The derivative is negative below $t_0$ and positive above it, so $t_0$ minimizes the expression on the positive real line. When $t_0\le1$, substitution gives a constant times $R_p^{p(\alpha+1)/(\alpha+p)}$. If $t_0>1$, use the trivial bound that regret is at most one; enlarging the constant $K$ gives the displayed result in this range as well. If $R_p=0$, then $\hat\eta=\eta$ almost surely, so the plug-in regret is zero; this case does not use a threshold minimizer at $t=0$.

For $p=1$, the threshold bound is $Ct^{\alpha+1}+2R_1$ for every $t>0$. Letting $t\downarrow0$ shows that regret is at most $2R_1$. This completes the proof. $\square$

The exponent $q=p(\alpha+1)/(\alpha+p)$ increases with $\alpha$ when $p>1$, since $$ \frac{d}{d\alpha}\left(\frac{p(\alpha+1)}{\alpha+p}\right) =\frac{p(p-1)}{(\alpha+p)^2}>0. $$ At $\alpha=0$, $q=1$; as $\alpha$ grows without bound, $q$ approaches $p$. Thus a weak margin condition gives a regret bound linear in the $L_p$ error scale, while a stronger condition permits a higher power of that error. The case $p=1$ remains linear for every exponent.

Worked Examples Across Margin Exponents

Worked Example: Exponent Zero and Boundary Mass

Let $X$ take values $a$ and $b$, each with probability $1/2$, and set $\eta(a)=1/2$ and $\eta(b)=0.8$. Then $\Delta(a)=0$ and $\Delta(b)=|1.6-1|=0.6$. For $0<t<0.6$, $P(\Delta\le t)=1/2$; for $0.6\le t\le1$, $P(\Delta\le t)=1$. Hence the exponent-zero condition holds with $C=1$, but no positive exponent can hold: for every $t>0$, $P(\Delta\le t)\ge1/2$, which cannot be bounded by $Ct^\alpha$ for all sufficiently small $t$ when $\alpha>0$.

Suppose the regression estimate has $R_2=0.1$. The threshold bound for $\alpha=0$, $C=1$, and $p=2$ is $t+0.04/t$. Its derivative is $1-0.04/t^2$, so its minimizer is $t=0.2$. This is in the allowed interval, and the bound is $0.2+0.04/0.2=0.4$. The margin assumption has not ruled out substantial boundary mass; the resulting guarantee is only of order $R_2$, rather than a higher power.

Worked Example: Linear Margin Behavior

Let $X$ be uniform on $[-1,1]$, and define $\eta(x)=(1+x)/2$. Then $\Delta(X)=|X|$. For $0\le t\le1$, the uniform density is $1/2$, so $$ P(\Delta\le t)=P(-t\le X\le t)=\frac{2t}{2}=t. $$ This distribution satisfies the margin condition with $\alpha=1$ and $C=1$.

For $p=2$ and $R_2=0.1$, the threshold bound is $t^2+0.04/t$. Its derivative is $2t-0.04/t^2$, which vanishes when $2t^3=0.04$, or $t^3=0.02$. Thus $t=0.02^{1/3}$, approximately $0.2714$, which is within $(0,1]$. The bound is approximately $0.2714^2+0.04/0.2714=0.0737+0.1474=0.2211$. The rate theorem gives the power $2(1+1)/(2+1)=4/3$ of $R_2$, an improvement over the exponent-zero power of one.

Worked Example: A Stronger Margin Exponent

Let $U$ have density $2u$ on $[0,1]$, set $X=U$, and define $\eta(x)=(1+x)/2$. Then $\Delta=U$. For $0\le t\le1$, $$ P(\Delta\le t)=\int_0^t 2u\,du=t^2. $$ The margin condition therefore holds exactly with $\alpha=2$ and $C=1$.

With $p=2$ and $R_2=0.1$, the threshold bound is $t^3+0.04/t$. Its derivative is $3t^2-0.04/t^2$. Setting it to zero gives $3t^4=0.04$, so $t=(1/75)^{1/4}$, approximately $0.3398$, again within the allowed interval. The two terms are approximately $0.0392$ and $0.1177$, for a total bound of $0.1569$. The rate exponent is $2(2+1)/(2+2)=3/2$. This is stronger than the exponent $4/3$ for the preceding margin condition, because the probability of being close to the boundary decreases more quickly.

How to Read the Rate—and a Common Pitfall

For $p=2$, the rate power is $2(\alpha+1)/(\alpha+2)$. It equals $1$ at $\alpha=0$, $4/3$ at $\alpha=1$, and $3/2$ at $\alpha=2$; it approaches $2$ as $\alpha$ increases. For example, if $R_2$ is of order $n^{-1/4}$, these powers yield regret rates of order $n^{-1/4}$, $n^{-1/3}$, and $n^{-3/8}$, respectively. The regression accuracy alone does not determine which rate applies: the distribution must also satisfy the corresponding margin condition.

Common pitfall: An exponent-zero margin condition does not mean the boundary has zero probability, nor does it imply that $P(\Delta\le t)$ shrinks with $t$. It says only that this probability is bounded by a constant. The correction is to retain the near-boundary regret term $Ct^{\alpha+1}$, which becomes $Ct$ at $\alpha=0$, and optimize it against the estimation-error term.

A second optimization error is to substitute $R_p=0$ into a positive-error formula for the minimizing threshold and claim that the minimizer is $t=0$. The allowed thresholds satisfy $t>0$, so zero is not an admissible minimizer. The correct argument handles $R_p=0$ separately: zero $L_p$ error means $\hat\eta=\eta$ almost surely, and the regret is exactly zero.

Key takeaway: Under an $L_p$ regression error $R_p$, the plug-in regret rate for $p>1$ has power $p(\alpha+1)/(\alpha+p)$. Exponent zero gives no small-margin probability decay and only a linear power of $R_p$; stronger margin exponents yield higher powers.

Check Your Understanding

Use the threshold bound and rate exponent to answer each question.

Why does an exponent-zero margin condition allow positive probability at $\Delta=0$, while a positive exponent does not?
For $p=2$, calculate the regret-rate power when $\alpha=3$.
With $p=2$, $\alpha=1$, and $C=1$, write the threshold bound as a function of $t$ and $R_2$.
Why must the case $R_p=0$ be handled separately from the positive-error threshold optimization?
If two distributions have the same regression error rate but different valid margin exponents, which one gives the sharper regret guarantee, and why?