Margin Conditions for Kernel Classification

Why the Margin Near One Half Matters

In binary classification, the conditional probability \(\eta(x)=P(Y=1\mid X=x)\) determines the Bayes decision: predict class 1 when \(\eta(x)\) is above one half and class 0 when it is below. A score estimate can make mistakes near this threshold even when its numerical error is small. Far from the threshold, a larger error may be needed to change the predicted class.

A margin condition describes how much feature-distribution mass lies near the decision threshold. It does not require a particular kernel or estimation method. Rather, it quantifies how sensitive classification is to errors in a probability-scale score, and so helps translate score accuracy into classification-risk accuracy.

The condition is substantive when \(q>0\): it implies there is no positive probability mass exactly at the threshold. Indeed, for every \(t>0\), \(P(Z=0)\le P(Z\le t)\le At^q\), and letting \(t\) decrease to zero gives \(P(Z=0)=0\). A common alternative states the condition only for \(0<Z\le t\). That version allows mass at exact ties, which contributes no excess classification risk but must be treated separately when counting all disagreements.

Reading the Condition

A larger exponent means that the probability mass in a small threshold neighborhood is forced to decrease more rapidly. For example, an exponent of one gives an upper bound proportional to the width \(t\); an exponent of two gives an upper bound proportional to \(t^2\). The exponent is not necessarily unique: a distribution that has very little mass near the threshold may satisfy more than one such bound, with different constants.

The condition concerns the distribution of \(\eta(X)\), not the density of \(X\) by itself. It combines the geometry of the decision boundary, the way the conditional probability changes around that boundary, and how the covariates are distributed in those regions.

From Score Error to Vulnerable Mass

Let \(g:\mathcal X\to[0,1]\) be a measurable probability-scale score, and classify using \(h_g(x)=1\{g(x)\ge1/2\}\). Let \(h^*(x)=1\{\eta(x)\ge1/2\}\) be a Bayes classifier. If these rules disagree at \(x\), the score must have crossed the threshold relative to \(\eta(x)\). Consequently, \(|g(x)-\eta(x)|\ge|\eta(x)-1/2|\).

Proof. On the disagreement event, the threshold-crossing inequality gives \(Z\le|g(X)-\eta(X)|\le\varepsilon\). Thus the disagreement event is contained in \(\{Z\le\varepsilon\}\). Applying the margin condition gives \(P(h_g(X)\ne h^*(X))\le P(Z\le\varepsilon)\le A\varepsilon^q\). At \(\varepsilon=0\), the same conclusion follows because the condition implies \(P(Z=0)=0\). \(\square\)

This result bounds the mass of potentially changed decisions. Classification risk gives greater weight to errors farther from the boundary, so an excess-risk bound can be sharper than a disagreement-probability bound. For a classifier \(h\), write \(R(h)=P(h(X)\ne Y)\). Conditioning on \(X=x\), predicting 0 has error probability \(\eta(x)\), while predicting 1 has error probability \(1-\eta(x)\). Choosing the worse of these two decisions incurs conditional excess error \(|2\eta(x)-1|\). Hence

The identity also shows why exact ties do not affect excess risk: when \(Z=0\), the conditional error is the same for either prediction.

A Bound from an Average Score Error

A uniform error guarantee is often unavailable. A useful alternative is to control the \(p\)th moment of the probability-score error, for some \(p\ge1\). The margin condition and a threshold argument then separate points close to the boundary from points where crossing the boundary requires a larger score error.

Proof. Write \(e(X)=g(X)-\eta(X)\) and \(D=\{h_g(X)\ne h^*(X)\}\). As above, \(D\subseteq\{Z\le|e(X)|\}\). Split the excess-risk identity according to whether \(Z\le t\) or \(Z>t\). On the first part, \(Z\le t\), so

The condition \(q>0\) ensures \(P(Z=0)=0\), so omitting \(Z=0\) does not change this expectation. On the second part, \(D\) implies \(|e(X)|\ge Z>t\). Therefore \(Z\le |e(X)|^p/Z^{p-1}\le |e(X)|^p/t^{p-1}\), and

Adding the two bounds proves the inequality for every \(0<t\le1/2\). For \(M>0\), choose \(t=M^{1/(p+q)}\) when this is at most \(1/2\). Both terms then have the power \(M^{(q+1)/(p+q)}\), giving the stated bound. If \(M^{1/(p+q)}>1/2\), the right-hand side \(2(A+1)M^{(q+1)/(p+q)}\) is at least 1, while excess risk is at most 1. If \(M=0\), then \(g(X)=\eta(X)\) almost surely, so the induced classifier is Bayes-optimal almost surely. \(\square\)

Common Pitfall and Practical Meaning

Common mistake: “The score error is small on average, so few classifications can be wrong.” This reasoning ignores where the score errors occur. Even tiny errors can change many decisions if much of the covariate distribution has conditional probabilities close to one half. Conversely, a less accurate score can still classify well when little probability mass lies near the threshold.

The margin condition supplies the missing distributional information. Under a uniform error bound, it directly limits the mass of points whose decisions are vulnerable. Under an \(L^p\) error bound, the derived result shows how that limited near-boundary mass combines with the probability of larger errors. The resulting guarantee is about classification excess risk, not about whether the estimated score is uniformly close to the true conditional probability.

The condition is an assumption about the data distribution, not a property automatically guaranteed by a kernel choice. Its exponent and constant describe the difficulty of classification near the Bayes boundary. They can clarify why two settings with similar score errors may have different classification performance, while remaining distinct from assumptions that directly control the variance of a loss or score.