Bernstein Exponents from Classification Noise

From Classification Noise to a Variance Bound

For a classifier, the zero-one excess loss is nonzero precisely when its prediction disagrees with a Bayes classifier. How often that happens is important, but the disagreement probability alone does not describe the cost of each error: mistakes made where the two classes are nearly equally likely are less costly than mistakes made where one class is much more likely. A margin condition quantifies how much probability lies near that ambiguous region. This tutorial derives how that condition controls the variance of zero-one excess loss.

Definition: Let \((X,Y)\) have a fixed distribution, with \(Y\in\{0,1\}\), and write \(\eta(x)=P(Y=1\mid X=x)\). Use the tie convention \(h^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}\) for a Bayes classifier. Define the classification margin by \(M(x)=|2\eta(x)-1|\), so \(0\le M(x)\le 1\). For a measurable classifier \(h\), define its zero-one excess-loss random variable by \(\mathcal{L}_h=\mathbf{1}\{h(X)\ne Y\}-\mathbf{1}\{h^*(X)\ne Y\}\). Its expectation \(r(h)=E[\mathcal{L}_h]\) is the excess risk, and its variance is \(\operatorname{Var}(\mathcal{L}_h)\).

The convention at \(\eta(x)=1/2\) fixes which Bayes classifier is used at a tie. Since \(M(x)=0\) there, disagreements at such points have zero conditional excess risk. Under a positive-exponent margin condition, the set of ties also has probability zero, as shown below.

The Conditional Excess-Risk Identity

The link between margin and excess risk follows by conditioning on \(X\). If \(h(x)=h^*(x)\), the conditional excess loss is zero. If they disagree and \(\eta(x)>1/2\), then \(h^*(x)=1\) and \(h(x)=0\): the conditional error probabilities are \(\eta(x)\) for \(h\) and \(1-\eta(x)\) for \(h^*\), with difference \(2\eta(x)-1\). If they disagree and \(\eta(x)<1/2\), the corresponding difference is \(1-2\eta(x)\). At a tie this difference is zero. Thus the conditional excess risk is \(M(x)\) on disagreement and zero otherwise.

Identity: For every measurable classifier \(h\), \[ r(h)=E\!\left[M(X)\mathbf{1}\{h(X)\ne h^*(X)\}\right]. \] Also, \(\mathcal{L}_h^2=\mathbf{1}\{h(X)\ne h^*(X)\}\) almost surely.

For the second identity, when the classifiers agree their losses are identical. When they disagree, the binary label \(Y\) must agree with exactly one of their predictions, so the difference between their zero-one losses is either \(1\) or \(-1\); its square is \(1\). These identities reduce the variance question to controlling disagreement probability.

Worked Example: A Uniform Margin and a Threshold Classifier

Let \(X\) be uniform on \([0,1]\), and set \(\eta(x)=(1+x)/2\). Then \(M(x)=x\), and \(h^*(x)=1\) for every \(x\), including \(x=0\) under the tie convention. For \(0<s\le 1\), consider \(h_s(x)=0\) for \(0\le x<s\) and \(h_s(x)=1\) otherwise.

The classifiers disagree on an interval of probability \(s\). The margin distribution satisfies \(P(M(X)\le t)=t\) for \(0\le t\le1\), a Tsybakov margin condition with exponent \(\alpha=1\) and constant \(C=1\). The excess risk is \[ r(h_s)=\int_0^s x\,dx=\frac{s^2}{2}. \] Since \(\mathcal{L}_{h_s}^2\) is the indicator of disagreement, \(E[\mathcal{L}_{h_s}^2]=s\). Therefore \[ \operatorname{Var}(\mathcal{L}_{h_s})=s-\left(\frac{s^2}{2}\right)^2=s-\frac{s^4}{4}. \] The general bound derived below is \(2r(h_s)^{1/2}=\sqrt{2}\,s\). It holds because \(s-s^4/4\le s\le\sqrt{2}\,s\). The calculation also shows why small excess risk can coexist with a larger disagreement probability: the disagreements occur near the boundary, where their margins are small.

From a Margin Condition to Disagreement Probability

A Tsybakov margin condition bounds the probability of observing a small margin. The form used here assumes constants \(C>0\) and \(\alpha>0\) such that

Definition: The distribution satisfies a Tsybakov margin condition with exponent \(\alpha>0\) and constant \(C\) if \[ P(M(X)\le t)\le C t^\alpha \qquad \text{for every }0<t\le1. \]

Write \(q(h)=P(h(X)\ne h^*(X))\). For any \(t\in(0,1]\), split disagreement into the event where the margin is at most \(t\) and the event where it is greater than \(t\). The first part has probability at most \(Ct^\alpha\). On the second part, each disagreement contributes more than \(t\) to the margin-weighted excess risk, so its probability is at most \(r(h)/t\). Consequently,

q(h)\le P(M(X)\le t)+P(h(X)\ne h^*(X),\,M(X)>t) \le Ct^\alpha+\frac{r(h)}{t}.

When \(r(h)>0\), choose \(t=(r(h)/C)^{1/(\alpha+1)}\). This is an admissible threshold: \(r(h)\le1\), since it is an expectation of a nonnegative quantity bounded by one, and \(C\ge1\), since the margin condition at \(t=1\) implies \(1\le C\). Substitution gives

q(h)\le 2C^{1/(\alpha+1)}r(h)^{\alpha/(\alpha+1)}.

If \(r(h)=0\), the same conclusion follows by taking \(t\) down to zero in \(q(h)\le Ct^\alpha+r(h)/t\), which gives \(q(h)=0\). This also shows that \(P(M(X)=0)=0\): for every \(t>0\), \(P(M(X)=0)\le P(M(X)\le t)\le Ct^\alpha\), and the right-hand side tends to zero. Thus any tie-set has probability zero under this condition.

Worked Example: A Discrete Margin Distribution

Suppose \(X\) takes a value \(a\) with probability \(1/16\) and a value \(b\) with probability \(15/16\). Let \(\eta(a)=5/8\) and \(\eta(b)=1\). The Bayes classifier predicts 1 at both points; the margins are \(M(a)=1/4\) and \(M(b)=1\).

For \(t<1/4\), \(P(M\le t)=0\). For \(1/4\le t<1\), it equals \(1/16\), which is at most \(t^2\), since \(t^2\ge(1/4)^2=1/16\). At \(t=1\), the probability is 1. Hence the margin condition holds with \(\alpha=2\) and \(C=1\).

Let \(h\) predict 0 at \(a\) and 1 at \(b\). Its disagreement probability is \(q(h)=1/16\), and \[ r(h)=E[M(X)\mathbf{1}\{h(X)\ne h^*(X)\}]=\frac{1}{16}\cdot\frac14=\frac{1}{64}. \] The second moment of its excess-loss variable is \(1/16\), so \[ \operatorname{Var}(\mathcal{L}_h)=\frac{1}{16}-\left(\frac{1}{64}\right)^2 =\frac{255}{4096}. \] The general bound on disagreement is \(2(1/64)^{2/3}=1/8\), and the variance is no larger than \(q(h)=1/16<1/8\). This example checks the exponent \(2/3\) without requiring a continuous margin distribution.

The Bernstein Variance Bound

The disagreement bound implies the desired variance inequality. Variance is at most the second moment, and the second moment of the excess-loss variable is exactly the disagreement probability. Combining these facts yields the theorem.

Theorem: Suppose the Tsybakov margin condition holds with \(C>0\) and \(\alpha>0\). For every measurable classifier \(h\), \[ \operatorname{Var}(\mathcal{L}_h)\le 2C^{1/(\alpha+1)}r(h)^\beta, \qquad \beta=\frac{\alpha}{\alpha+1}. \]

Proof. Since \(\operatorname{Var}(\mathcal{L}_h)=E[\mathcal{L}_h^2]-(E[\mathcal{L}_h])^2\), the second-moment identity gives

\operatorname{Var}(\mathcal{L}_h) \le E[\mathcal{L}_h^2] =q(h) \le 2C^{1/(\alpha+1)}r(h)^{\alpha/(\alpha+1)}.

The disagreement inequality was proved for \(r(h)>0\); when \(r(h)=0\), it gives \(q(h)=0\), so the variance is also zero. The asserted bound therefore holds in both cases. \(\square\)

A Bernstein variance condition is an inequality that bounds the variance of a loss difference by a constant times a power of its mean excess loss. Here the random variable is specifically the zero-one excess loss, and the power is \(\beta=\alpha/(1+\alpha)\). The condition is distribution-dependent: the margin assumption is on the distribution of \(X\) and its conditional label probabilities, while the resulting inequality holds for every measurable classifier under that distribution.

Worked Example: The Exponent and Its Sharpness

For any fixed \(\alpha>0\), let \(X\) be uniform on \([0,1]\), put \(M(x)=x^{1/\alpha}\), and define \(\eta(x)=(1+M(x))/2\). Then \(P(M(X)\le t)=t^\alpha\) for \(0\le t\le1\), so the margin condition holds with \(C=1\). Again \(h^*(x)=1\) everywhere, including \(x=0\), where \(\eta(0)=1/2\) and the tie convention selects 1.

For \(0<s\le1\), let \(h_s\) predict 0 on \(0\le x<s\) and 1 otherwise. Its disagreement probability is \(s\), and its excess risk is \[ r(h_s)=\int_0^s x^{1/\alpha}\,dx =\frac{\alpha}{\alpha+1}s^{1+1/\alpha}. \] Thus \(s=\bigl((\alpha+1)r(h_s)/\alpha\bigr)^{\alpha/(\alpha+1)}\). The variance is \(s-r(h_s)^2\), so for small \(s\) it is asymptotic to \(s\), and therefore has order \(r(h_s)^{\alpha/(\alpha+1)}\). In particular, a universal bound with a strictly larger power \(\beta'>\alpha/(\alpha+1)\) cannot hold for this model with a fixed finite constant: the ratio of the variance to \(r(h_s)^{\beta'}\) grows without bound as \(s\) decreases to zero. The exponent supplied by the theorem is therefore generally sharp.

Interpretation and a Common Pitfall

The exponent \(\beta\) lies between zero and one. A larger margin exponent \(\alpha\) means less probability can accumulate near zero margin, and it produces a larger Bernstein exponent, approaching one as \(\alpha\) grows. This is the precise bridge from a distributional statement about classification noise to a moment bound on excess loss. The theorem itself does not establish a learning rate for any particular procedure; using the variance bound to analyze a predictor class requires additional arguments.

Pitfall: replacing variance by the mean squared excess loss. The excess-loss variable can equal \(-1\) as well as \(1\), so its expectation is not its second moment. The correct calculation is \(\operatorname{Var}(\mathcal{L}_h)=E[\mathcal{L}_h^2]-r(h)^2\), with \(E[\mathcal{L}_h^2]=q(h)\). Dropping the variance correction is safe only as an upper bound, not as an equality.
Pitfall: reversing the exponent relationship. The margin exponent is not itself the variance exponent. Splitting at threshold \(t\) gives \(Ct^\alpha+r/t\); balancing these terms makes \(t\) proportional to \(r^{1/(\alpha+1)}\), and the resulting power is \(\alpha/(\alpha+1)\).
Pitfall: overlooking ties. At \(\eta(x)=1/2\), the stated convention predicts 1. The conditional excess risk is still zero because \(M(x)=0\). Under \(\alpha>0\), the margin condition forces the tie-set to have probability zero, but the pointwise convention remains well-defined.

Key takeaway: Under a Tsybakov margin condition with exponent \(\alpha>0\), disagreement probability is at most a constant times excess risk to the power \(\alpha/(1+\alpha)\). Since the zero-one excess-loss variance is no greater than disagreement probability, its Bernstein exponent is \(\alpha/(1+\alpha)\) as well.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

Why is the squared zero-one excess-loss variable equal to the indicator that \(h(X)\) and \(h^*(X)\) disagree?
In the split \(q(h)\le Ct^\alpha+r(h)/t\), what choice of \(t\) balances the two terms, and what power of \(r(h)\) results?
If the margin exponent is \(\alpha=3\), what is the corresponding Bernstein exponent?
Why does a positive-exponent margin condition imply that the probability of an exact tie, \(M(X)=0\), is zero?
In the discrete example, verify directly that \(P(M\le t)\le t^2\) for \(1/4\le t<1\).