Plug-In Classification Rate Derivation Workshop

From Regression Guarantees to Classification Rates

A plug-in classifier first estimates a regression function and then thresholds that estimate. A regression guarantee alone does not say how often this procedure makes classification errors: errors far from the decision boundary matter more than errors near it. A margin condition quantifies how much probability lies near the boundary, allowing a regression-error bound and boundary information to work together.

This tutorial works through that conversion in two forms. An integrated \(L_p\) error guarantee gives a rate by splitting observations according to their distance from the boundary. A uniform deviation guarantee gives a simpler rate directly. In both cases, the exponent depends on the stated margin condition; it should be calculated, not guessed.

Definition: In binary classification, let \(\eta(x)=P(Y=1\mid X=x)\), and let \(\hat{\eta}\) be an estimate based on training data. The plug-in threshold rule is \(\hat{g}(x)=\mathbf{1}\{\hat{\eta}(x)\geq 1/2\}\). Write \(g^*(x)=\mathbf{1}\{\eta(x)\geq 1/2\}\) for the corresponding optimal rule. For the classification risk \(R\), the plug-in excess risk has the standard representation \(R(\hat{g})-R(g^*)=2E_X[|\eta(X)-1/2|\mathbf{1}\{\hat{g}(X)\ne g^*(X)\}]\), conditional on the fitted estimate. When \(\hat{\eta}\) is random, we also average this expression over the training data.

The boundary is the set where \(\eta(x)=1/2\). A margin condition limits the probability mass near this set.

Definition: The margin condition with exponent \(\alpha\geq 0\) and constant \(C>0\) is \(P_X(|\eta(X)-1/2|\leq t)\leq Ct^\alpha\) for every \(t>0\). It says how quickly the probability of being close to the decision boundary can shrink as the neighborhood narrows. The case \(\alpha=0\) permits substantial boundary mass; larger exponents impose a stronger restriction near the boundary.

The Integrated-Error Bound

Suppose the regression estimate is controlled in integrated \(L_p\) error, for some \(p\geq 1\). The expectation below is over both the training data and a fresh test covariate. This formulation allows the fitted function to be random while applying the margin condition to the population distribution of \(X\).

Theorem: Suppose the margin condition holds with \(\alpha\geq 0\) and constant \(C\), and suppose \(E_{D,X}[|\hat{\eta}(X)-\eta(X)|^p]\leq \delta^p\) for some \(p\geq 1\) and \(\delta>0\). Then the expected plug-in excess risk satisfies \(E_D[R(\hat{g})-R(g^*)]\leq 2(C+1)\delta^{p(\alpha+1)/(p+\alpha)}\).

The exponent comes from a threshold \(t\) used to divide observations into two groups: those close to the boundary and those where a classification disagreement requires a larger regression error. Here is the full argument.

Relate disagreement to estimation error.
Write \(m(X)=|\eta(X)-1/2|\) and \(e(X)=|\hat{\eta}(X)-\eta(X)|\). If the two threshold rules disagree, then \(e(X)\geq m(X)\): an estimate must move across the threshold \(1/2\) by at least the true function's distance from it.

Split at distance \(t\).
On \(m(X)\leq t\), bound the margin weight by \(t\) and use the margin condition. On \(m(X)>t\), disagreement implies \(e(X)>t\), and \(m(X)\leq e(X)\).

Balance the two contributions.
The near-boundary term is at most a constant times \(t^{\alpha+1}\), while the other term is controlled by the \(p\)th error moment divided by \(t^{p-1}\). Set \(t=\delta^{p/(p+\alpha)}\) to match their powers of \(\delta\).

For completeness, the split yields the bound explicitly. On the event \(m(X)\leq t\), the risk representation and margin condition give a contribution at most \(2tP_X(m(X)\leq t)\leq 2Ct^{\alpha+1}\). On the event \(m(X)>t\), disagreement implies \(e(X)\geq m(X)>t\), and \(m(X)\leq e(X)\). Since \(p\geq1\), \(e\leq e^p/t^{p-1}\) whenever \(e>t\). Therefore this contribution is at most \(2\delta^p/t^{p-1}\). Together,

E_D[R(\hat{g})-R(g^*)] \leq 2\left(Ct^{\alpha+1}+\frac{\delta^p}{t^{p-1}}\right).

Choose \(t=\delta^{p/(p+\alpha)}\). Then \(t^{\alpha+1}=\delta^{p(\alpha+1)/(p+\alpha)}\), and \(\delta^p/t^{p-1}=\delta^{p-p(p-1)/(p+\alpha)} =\delta^{p(\alpha+1)/(p+\alpha)}\). Substitution proves the stated result. This choice balances the powers; it need not minimize the precise constant. \(\square\)

Worked Rate Calculations

Worked Example: An \(L_2\) Guarantee with Linear Margin Behavior

Suppose \(P_X(|\eta(X)-1/2|\leq t)\leq 3t\), so \(\alpha=1\) and \(C=3\). Assume the integrated squared error satisfies \(E_{D,X}|\hat{\eta}(X)-\eta(X)|^2\leq 16n^{-1/2}\). Find the resulting excess-risk rate.

Here \(p=2\). The error-moment bound is \(\delta^2=16n^{-1/2}\), so \(\delta=4n^{-1/4}\). The theorem's exponent is \(p(\alpha+1)/(p+\alpha)=2(2)/(2+1)=4/3\).

Thus \(E_D[R(\hat{g})-R(g^*)]\leq 2(3+1)(4n^{-1/4})^{4/3} =8\cdot 4^{4/3}n^{-1/3}\). The rate is \(n^{-1/3}\). The numerical bound may exceed one for small \(n\); since excess risk is at most one, it can always be combined with that trivial bound.

Worked Example: A Uniform Deviation Guarantee

Suppose the margin condition has \(\alpha=2\), \(C=5\), and an event of probability at least \(1-n^{-2}\) guarantees \(\sup_x|\hat{\eta}(x)-\eta(x)|\leq 2n^{-1/6}\). Find a high-probability regret bound and an expected-risk bound.

On the stated event, a disagreement can occur only where \(|\eta(x)-1/2|\leq 2n^{-1/6}\). Otherwise the estimate cannot move far enough to cross \(1/2\). The excess risk on the event is therefore at most \(2(2n^{-1/6})P_X(|\eta(X)-1/2|\leq 2n^{-1/6})\).

Using the margin condition, this is at most \(2C(2n^{-1/6})^{\alpha+1} =10(2n^{-1/6})^3 =80n^{-1/2}\). This is the high-probability bound on the event. For expected risk, the complementary event contributes at most \(n^{-2}\), since excess risk is at most one. Hence \(E_D[R(\hat{g})-R(g^*)]\leq 80n^{-1/2}+n^{-2}\).

Uniform-error result: If \(\sup_x|\hat{\eta}(x)-\eta(x)|\leq a\), then under the margin condition the plug-in excess risk is at most \(2Ca^{\alpha+1}\). Indeed, disagreement implies \(|\eta(x)-1/2|\leq a\); on this set the margin weight is at most \(a\), so the risk representation gives at most \(2aP_X(|\eta(X)-1/2|\leq a)\leq 2Ca^{\alpha+1}\). \(\square\)

Worked Example: Comparing Two Integrated-Error Rates

Under the same margin condition with \(\alpha=1\) and \(C=2\), suppose method A has integrated squared error at most \(n^{-2/5}\), while method B has integrated squared error at most \(n^{-1/2}\). Compare the excess-risk bounds.

For both methods \(p=2\), and the excess-risk exponent on \(\delta\) is \(4/3\). Method A has \(\delta_A=n^{-1/5}\), because its stated guarantee is a bound on squared error. Its risk bound is \(2(C+1)\delta_A^{4/3}=6n^{-4/15}\).

Method B has \(\delta_B=n^{-1/4}\), so its risk bound is \(2(C+1)\delta_B^{4/3}=6n^{-1/3}\). For \(n>1\), \(n^{-1/3}<n^{-4/15}\), since \(1/3>4/15\). Thus method B yields the faster bound under these guarantees. This comparison concerns the stated upper bounds; it does not by itself prove that method B has smaller risk at every sample size.

Reading and Comparing the Rates

If the integrated \(L_p\) error scale is \(\delta_n\), the derived regret scale is \(\delta_n^{p(\alpha+1)/(p+\alpha)}\). In particular, an \(L_2\) guarantee is often reported as a mean squared error (MSE) bound. If \(\mathrm{MSE}\leq r_n\), then \(\delta_n=r_n^{1/2}\), and the regret rate is \(r_n^{(\alpha+1)/(2+\alpha)}\). This extra square root is essential.

A uniform deviation rate can be stronger than an integrated-error rate because it controls the estimate at every point, including points that have little population probability. Under a uniform bound \(a_n\), the regret rate is \(a_n^{\alpha+1}\). Do not compare these exponents without also checking what each guarantee measures, whether it holds in expectation or with high probability, and whether its constants depend on \(n\).

Common Mistakes

Using the MSE as though it were an \(L_2\) error scale. If \(E|\hat{\eta}-\eta|^2\leq r_n\), then \(\delta_n=r_n^{1/2}\), not \(r_n\). Apply the theorem to the second-moment bound or take its square root consistently.
Using the uniform rate formula for an integrated bound. The \(a^{\alpha+1}\) result requires a uniform deviation bound. An \(L_p\) moment guarantee instead requires the split and gives the exponent \(p(\alpha+1)/(p+\alpha)\) on \(\delta\).
Changing the margin exponent convention mid-calculation. Here \(\alpha\) is defined by \(P(|\eta(X)-1/2|\leq t)\leq Ct^\alpha\). Rates from a source using a different margin parameterization cannot be compared until the conventions are aligned.
Claiming a faster bound means a uniformly better classifier. The derivation compares guarantees under stated assumptions. It does not establish a pointwise ordering of two fitted rules or show that the assumptions hold in a particular application.

Key takeaway: For integrated \(L_p\) error scale \(\delta\), split at distance \(t\) from the boundary and balance \(t^{\alpha+1}\) against \(\delta^p/t^{p-1}\). For uniform error \(a\), use the direct boundary localization bound \(2Ca^{\alpha+1}\). Keep the error scale, margin convention, and probability mode explicit.

Check Your Understanding

Work through each question by identifying the guarantee, margin exponent, and threshold rule before calculating a rate.

If \(E|\hat{\eta}(X)-\eta(X)|^2\leq n^{-3/5}\) and \(\alpha=1\), what is the theorem's excess-risk rate?
For \(p=1\), what exponent does the integrated-error theorem give on \(\delta\), and why does the splitting term involving \(t^{p-1}\) simplify?
Under a uniform deviation bound \(a_n=n^{-1/4}\) and margin exponent \(\alpha=2\), what is the resulting regret rate?
Why does disagreement between the two threshold rules imply \(|\hat{\eta}(X)-\eta(X)|\geq|\eta(X)-1/2|\)?
Two methods have MSE bounds \(n^{-1/2}\) and \(n^{-2/3}\), respectively. Under \(\alpha=1\), compute their regret-rate exponents and identify which bound is faster.