Tutorials › Statistical Learning (Graduate) › Supremum-Error Bounds Under a Margin Condition

Home  /  Tutorials  /  Plug-In Classification and Margins

Plug-In Classification and Margins · Tutorial 499 of 989

Supremum-Error Bounds Under a Margin Condition

Learn how uniform regression accuracy and low probability near the Bayes threshold combine to control classification regret.

Intermediate 11 min read

What You'll Learn

  • Define the margin distribution using the distance from the Bayes threshold.
  • Prove that a uniform regression error confines classifier disagreement to a narrow margin region.
  • Derive the excess-risk bound and its dependence on the margin exponent.
  • Work through discrete and continuous examples with explicit constants.
  • Verify that the exponent alpha plus one is sharp in a worst-case family.
  • Distinguish a deterministic uniform guarantee from a high-probability guarantee.

Why Uniform Accuracy Can Give a Faster Risk Rate

A plug-in classifier estimates the probability of label 1 at each feature value and assigns the label according to whether that estimate exceeds one half. A uniform error bound says that the estimated probability is never more than a specified amount away from the true regression function. By itself, this does not tell us how often the classifier makes errors: that also depends on how much probability lies near the threshold, where even a small estimation error can change the predicted label.

A margin condition quantifies that probability. If little probability lies near the Bayes threshold, a uniform estimation error of size \(\epsilon\) can cause disagreement only on a small set, and each disagreement has limited cost. Together these facts yield an excess-risk bound of order \(\epsilon^{\alpha+1}\), where \(\alpha\) is the margin exponent.

Definitions and Conventions

Let \((X,Y)\) be a random pair, with \(Y\in\{0,1\}\), and let \(\eta(x)=P(Y=1\mid X=x)\) be a measurable version of the regression function. For a measurable classifier \(g\), its risk is \(R(g)=P(g(X)\ne Y)\). Define the Bayes classifier \(g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}\); either label is optimal when \(\eta(x)=1/2\). For a measurable estimated regression function \(\hat\eta\), the plug-in classifier is \(\hat g(x)=\mathbf{1}\{\hat\eta(x)\ge 1/2\}\).

Definition: The margin at \(x\) is \(\Delta(x)=|2\eta(x)-1|\), which lies in \([0,1]\). A margin condition with exponent \(\alpha\ge 0\) and constant \(C\ge 1\) is $$ P(\Delta(X)\le t)\le C t^\alpha,\qquad 0<t\le 1. $$ This convention measures distance using \(|2\eta-1|\), not \(|\eta-1/2|\). The two quantities differ by a factor of 2.

The condition includes points exactly on the threshold. For \(\alpha>0\), it therefore rules out positive probability at \(\eta(X)=1/2\). The requirement \(C\ge 1\) is necessary at \(t=1\), since \(\Delta(X)\le 1\) always. When \(\alpha=0\), the condition is generally only a bounded-probability statement and does not imply that the boundary has zero probability.

The Excess-Risk Identity and the Main Bound

At a fixed feature value \(x\), predicting 1 has conditional error probability \(1-\eta(x)\), while predicting 0 has conditional error probability \(\eta(x)\). The Bayes classifier chooses the smaller of these two probabilities. Choosing the other label increases conditional error by \(|1-2\eta(x)|=\Delta(x)\). Integrating over \(X\) gives the exact identity

$$ R(g)-R(g^*)=E\!\left[\Delta(X)\mathbf{1}\{g(X)\ne g^*(X)\}\right]. $$

At a threshold tie, the two conditional errors are equal, so the identity holds whichever label is selected. In particular, classification regret is not the probability of disagreement alone: each disagreement is weighted by its margin.

Theorem: Suppose the margin condition holds with exponent \(\alpha\ge 0\) and constant \(C\ge 1\). If \(\|\hat\eta-\eta\|_\infty\le\epsilon\), then $$ R(\hat g)-R(g^*)\le 2^{\alpha+1}C\epsilon^{\alpha+1}. $$ Here the uniform bound means \(|\hat\eta(x)-\eta(x)|\le\epsilon\) for all relevant \(x\), or at least almost surely under the distribution of \(X\). The result also holds for \(\epsilon=0\), with regret zero.

Proof. Consider a feature value where \(\hat g(x)\ne g^*(x)\). If \(\eta(x)>1/2\), then \(g^*(x)=1\) and disagreement requires \(\hat\eta(x)<1/2\). Consequently,

$$ \eta(x)-\frac12\le \eta(x)-\hat\eta(x)\le|\eta(x)-\hat\eta(x)|\le\epsilon. $$

If \(\eta(x)<1/2\), then disagreement requires \(\hat\eta(x)\ge 1/2\), so

$$ \frac12-\eta(x)\le\hat\eta(x)-\eta(x)\le|\hat\eta(x)-\eta(x)|\le\epsilon. $$

At \(\eta(x)=1/2\), the margin is zero, so it already satisfies the same conclusion. Thus disagreement implies \(|\eta(x)-1/2|\le\epsilon\), or equivalently \(\Delta(x)\le 2\epsilon\). The excess-risk identity and \(\Delta(x)\le 2\epsilon\) on the disagreement set now give

$$ R(\hat g)-R(g^*)\le 2\epsilon\,P(\Delta(X)\le 2\epsilon). $$

When \(0<\epsilon\le 1/2\), apply the margin condition at \(t=2\epsilon\):

$$ R(\hat g)-R(g^*)\le 2\epsilon\,C(2\epsilon)^\alpha =2^{\alpha+1}C\epsilon^{\alpha+1}. $$

When \(\epsilon>1/2\), excess risk is at most 1, while \(2^{\alpha+1}C\epsilon^{\alpha+1}>1\), so the stated bound still holds. If \(\epsilon=0\), the estimated and true regression functions agree almost surely, their threshold decisions agree except possibly at ties, and ties have zero regret. This proves the result. \(\square\)

Worked Bounds in Concrete Models

Worked Example: A Discrete Margin Distribution

Suppose \(X\) has two possible values. At the first, with probability \(0.3\), let \(\eta(X)=0.53\). At the second, with probability \(0.7\), let \(\eta(X)=0.75\). The corresponding margins are \(0.06\) and \(0.50\). Verify a margin condition with \(\alpha=1\), then bound the regret when \(\epsilon=0.04\).

For \(0<t<0.06\), the margin probability is zero. For \(0.06\le t<0.50\), it is \(0.3\), and for \(0.50\le t\le 1\), it is 1. The condition holds with \(C=5\): at the first jump, \(0.3\le5(0.06)=0.3\); between the jumps, \(5t\ge0.3\); and above \(0.50\), \(5t\ge2.5\ge1\).

The theorem gives

$$ R(\hat g)-R(g^*)\le 2^2(5)(0.04)^2=20(0.0016)=0.032. $$

This bound allows for possible disagreement at the first feature value, since \(0.06\le2\epsilon=0.08\), but not at the second. It is a valid worst-case guarantee; it need not equal the regret of a particular estimate.

Worked Example: Integrating Regret in a Continuous Model

Let \(X\) be uniform on \([0,1]\), and set \(\eta(x)=0.25+0.5x\). Then \(\Delta(x)=|x-0.5|\). For \(0<t\le0.5\), the interval where \(\Delta(x)\le t\) has length \(2t\); for \(0.5<t\le1\), its probability is 1. Thus \(P(\Delta(X)\le t)\le2t\) for all \(0<t\le1\): the margin condition holds with \(\alpha=1\) and \(C=2\).

Take \(\hat\eta(x)=\eta(x)-0.1\), so the uniform error is \(\epsilon=0.1\). The true classifier switches at \(x=0.5\), while the estimated classifier switches at \(x=0.7\). They disagree for \(0.5\le x<0.7\), up to endpoints of probability zero. The exact excess risk is

$$ \int_{0.5}^{0.7}(x-0.5)\,dx =\int_0^{0.2}u\,du =\frac{(0.2)^2}{2} =0.02. $$

The general bound is \(2^2(2)(0.1)^2=0.08\). The direct calculation verifies the regret and shows why the theorem can be conservative: it bounds the margin throughout the disagreement region by its largest possible value there.

Worked Example: A Quadratic Margin Condition

Suppose \(X\) takes two values with margins \(0.12\) and \(0.60\), having probabilities \(0.1\) and \(0.9\), respectively. For \(t<0.12\), the margin probability is zero; for \(0.12\le t<0.60\), it is \(0.1\); and for \(0.60\le t\le1\), it is 1. A condition with \(\alpha=2\) and \(C=7\) holds: at the first jump \(7(0.12)^2=0.1008\ge0.1\), and at the second \(7(0.60)^2=2.52\ge1\). Between jumps, \(7t^2\) is no smaller than its value at the lower endpoint.

For a uniform error bound \(\epsilon=0.07\), the theorem yields

$$ R(\hat g)-R(g^*)\le 2^3(7)(0.07)^3 =56(0.000343) =0.019208. $$

The first margin, \(0.12\), is within \(2\epsilon=0.14\), so that point could be misclassified under the uniform guarantee. The larger margin \(0.60\) cannot be crossed by an error of this size.

Why the Exponent Is \(\alpha+1\), and Why It Cannot Generally Improve

The power has two sources. The margin condition says that the probability of the potentially affected region is at most a constant times \(\epsilon^\alpha\). Each disagreement in that region costs at most \(2\epsilon\) in conditional risk. Multiplying these bounds produces \(\epsilon^{\alpha+1}\). The next result shows that, without stronger assumptions, this exponent cannot be improved uniformly over distributions satisfying the margin condition.

Sharpness construction: Fix \(\alpha\ge0\) and \(0<\epsilon\le1\). Let \(X\) take values \(a,b\) with probabilities \(\epsilon^\alpha\) and \(1-\epsilon^\alpha\), respectively. Set \(\eta(a)=(1+\epsilon)/2\), \(\eta(b)=1\), and define \(\hat\eta(a)=\eta(a)-\epsilon=(1-\epsilon)/2\), \(\hat\eta(b)=1\). At \(a\), the margin is \(\epsilon\), and at \(b\) it is 1. The margin condition holds with \(C=1\): below \(\epsilon\) the probability is zero; from \(\epsilon\) up to 1 it is \(\epsilon^\alpha\le t^\alpha\); at \(t=1\) the probability is 1. The uniform estimation error is exactly \(\epsilon\) at \(a\) and zero at \(b\). The plug-in rule predicts 0 at \(a\), while the Bayes rule predicts 1, so the excess risk is $$ \epsilon\cdot\epsilon^\alpha=\epsilon^{\alpha+1}. $$ This family attains the same power as the upper bound, up to its constant. Thus a uniformly faster power cannot be guaranteed from the stated assumptions alone.

Common Pitfalls and Practical Interpretation

  • Using the wrong margin scale. Here \(\Delta=|2\eta-1|\), so disagreement implies \(\Delta\le2\epsilon\). If margin is instead defined as \(|\eta-1/2|\), the corresponding threshold is \(\epsilon\), and constants must be adjusted consistently.
  • Dropping the cost of disagreement. The probability of disagreement is not itself the excess risk. The exact identity weights each disagreement by \(\Delta(X)\), which is why the additional factor of \(\epsilon\) appears.
  • Reversing the direction of the condition. The useful assumption is an upper bound on the probability of lying near the threshold. Saying only that the margin is “usually large” is not a quantitative substitute.
  • Treating a high-probability guarantee as a deterministic one. The theorem applies on any event where the uniform error bound holds. If that event has probability at least \(1-\delta\), the risk bound holds on that event; a bound for unconditional expected regret must also account for its complement. Since excess risk is at most 1, one simple unconditional bound is \(2^{\alpha+1}C\epsilon^{\alpha+1}+\delta\).

The result is useful when a regression procedure supplies a uniform error guarantee and the feature distribution has little mass near the decision boundary. It converts those two ingredients into a classification-regret guarantee without requiring the estimate to be accurate enough to classify every feature value correctly. The margin assumption is substantive: substantial probability near the threshold can make even small regression errors consequential.

Check Your Understanding

Use the convention \(\Delta=|2\eta-1|\) in answering these questions.

  1. If the uniform regression error is at most \(\epsilon\), what inequality must hold for \(\Delta(X)\) whenever the plug-in and Bayes classifiers disagree?
  2. Under a margin condition with exponent \(\alpha\), identify the two factors whose product gives the power \(\epsilon^{\alpha+1}\).
  3. For \(\alpha=1\), \(C=3\), and \(\epsilon=0.05\), calculate the theorem's upper bound, assuming \(2\epsilon\le1\).
  4. Why does the exact excess-risk identity weight disagreement by the margin rather than just counting disagreement probability?
  5. In the sharpness construction, which feature value causes regret, and why is its probability chosen to depend on \(\epsilon\)?

Previous

Next

Back to Tutorials
Clinical Biostats