Converting Lp Regression Error Into Classification Regret

Why Regression Error Can Control Classification Regret

A plug-in classifier estimates the conditional probability of class 1 and predicts class 1 when that estimate is at least one half. Regression accuracy alone does not determine how often this rule makes a consequential mistake: errors far from the decision threshold can change a prediction, while small errors near the threshold may not. A margin condition quantifies how much probability mass lies near that threshold. Together with Markov's inequality, it turns an expected p-th-power regression error bound into a bound on expected classification regret.

We use a fresh test feature $X$, independent of the data used to construct the estimator $\hat\eta$. Write $\eta(x)=P(Y=1\mid X=x)$, and define the margin $\Delta(x)=|2\eta(x)-1|$, which takes values in $[0,1]$. The plug-in classifier is $\hat g(x)=1\{\hat\eta(x)\geq 1/2\}$, and the Bayes classifier is $g^*(x)=1\{\eta(x)\geq 1/2\}$. Ties are assigned to class 1; at a point where $\eta(x)=1/2$, either prediction has the same conditional risk.

Definition: A distribution satisfies a margin condition with constants $C>0$ and $\alpha>0$ if, for every $0<t\leq 1$, $$ P\bigl(\Delta(X)\leq t\bigr)\leq C t^\alpha. $$ The expected p-th-power regression error is $\delta=E_{\mathrm{train}}E_X[|\hat\eta(X)-\eta(X)|^p]$, where $p\geq1$; the outer expectation is over the training data and $E_X$ integrates over a fresh feature.

For a fixed classifier $g$, its risk is $R(g)=P(g(X)\ne Y)$. Conditional on $X=x$, predicting class 1 has error probability $1-\eta(x)$, while predicting class 0 has error probability $\eta(x)$. Choosing the less risky label gives $g^*$. The conditional risk difference between the two labels is $|2\eta(x)-1|=\Delta(x)$. Consequently, for any plug-in classifier,

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

This identity also holds for a classifier constructed from random training data, conditional on that data. It says that regret counts only disagreements with the Bayes rule, weighted by how costly the disagreement is at each feature value.

From Disagreement to Regression Error

If the estimated and true regression functions fall on opposite sides of one half, their difference must be at least the true function's distance from one half. In the margin notation, disagreement therefore requires regression error at least $\Delta(X)/2$. The factor of two appears because $\Delta=2|\eta-1/2|$.

Worked Example: Checking the Disagreement Condition

At a feature value $x$, suppose $\eta(x)=0.68$ and $\hat\eta(x)=0.43$. Then $\Delta(x)=|2(0.68)-1|=0.36$, and the two classifiers disagree: the Bayes rule predicts class 1 and the plug-in rule predicts class 0. Their regression error is $|0.43-0.68|=0.25$, which exceeds $\Delta(x)/2=0.18$, as required.

More generally, if $\eta(x)>1/2$ and $\hat\eta(x)<1/2$, then $\eta(x)-\hat\eta(x)>\eta(x)-1/2=\Delta(x)/2$. If $\eta(x)<1/2$ and $\hat\eta(x)\geq1/2$, then $\hat\eta(x)-\eta(x)\geq1/2-\eta(x)=\Delta(x)/2$. Thus disagreement implies the stated error threshold in either direction.

The Regret Bound

Split possible test features into those with margin at most $t$ and those with larger margin. The first set has limited total regret because its margins are small, and the margin condition limits its probability. On the second set, disagreement requires an error large enough for Markov's inequality to be informative.

Theorem: Suppose the margin condition holds with $C>0$ and $\alpha>0$. For a plug-in classifier based on an estimator $\hat\eta$, let $p\geq1$ and suppose $\delta=E_{\mathrm{train}}E_X|\hat\eta(X)-\eta(X)|^p<\infty$. Then, for every $0<t\leq1$, $$ E_{\mathrm{train}}\!\left[R(\hat g)-R(g^*)\right] \leq C t^{\alpha+1}+2^p\delta\,t^{1-p}. $$

Proof. Fix $t\in(0,1]$. The contribution to regret from $\Delta(X)\leq t$ is at most $tP(\Delta(X)\leq t)$, which is at most $Ct^{\alpha+1}$. For the remaining features, condition on $X=x$ and use the independence of the test feature from the training data. The disagreement implication and Markov's inequality give, whenever $\Delta(x)>t$,

P_{\mathrm{train}}\bigl(\hat g(x)\ne g^*(x)\bigr) \leq P_{\mathrm{train}}\!\left(|\hat\eta(x)-\eta(x)|\geq \frac{\Delta(x)}{2}\right) \leq \frac{2^p E_{\mathrm{train}}|\hat\eta(x)-\eta(x)|^p}{\Delta(x)^p}.

The resulting conditional regret contribution is at most $2^p E_{\mathrm{train}}|\hat\eta(x)-\eta(x)|^p\Delta(x)^{1-p}$. Since $p\geq1$ and $\Delta(x)>t$, we have $\Delta(x)^{1-p}\leq t^{1-p}$. Integrate over $X$, then over the training data. The integrands are nonnegative, so these integrations are valid by Tonelli's theorem. The high-margin contribution is at most $2^p\delta t^{1-p}$. Adding the low-margin contribution proves the result. $\square$

Worked Example: A Two-Point Feature Distribution

Let $X$ take values $a$ and $b$ with probabilities $0.7$ and $0.3$, respectively. Suppose $\eta(a)=0.8$, $\eta(b)=0.52$, and the fitted function has values $\hat\eta(a)=0.7$, $\hat\eta(b)=0.4$. At $a$ the classifiers agree; at $b$ they disagree. The exact regret is therefore $0.3|2(0.52)-1|=0.3(0.04)=0.012$.

The margins are $0.6$ at $a$ and $0.04$ at $b$. The margin condition holds with $\alpha=1$ and $C=7.5$: for $t<0.04$, the probability is zero; for $0.04\leq t<0.6$, it is $0.3\leq7.5t$; and for $0.6\leq t\leq1$, it is $1\leq7.5t$.

The expected squared regression error (here the fit is deterministic) is $0.7(0.7-0.8)^2+0.3(0.4-0.52)^2=0.7(0.01)+0.3(0.0144)=0.01132$. Taking $p=2$ and $t=0.1$, the theorem gives the bound $7.5(0.1)^2+4(0.01132)(0.1)^{-1}=0.075+0.4528=0.5278$. This is much larger than the exact regret $0.012$, but it is a valid upper bound.

Choosing the Margin Threshold

The theorem holds for every threshold $t$, so a useful bound chooses $t$ to balance the two terms. For $p>1$, differentiating $Ct^{\alpha+1}+2^p\delta t^{1-p}$ gives the unconstrained minimizer

t_*=\left(\frac{2^p(p-1)\delta}{C(\alpha+1)}\right)^{1/(\alpha+p)}.

When $0<t_*\leq1$, substitution gives the bound $C(\alpha+p)t_*^{\alpha+1}/(p-1)$. In particular, for fixed $C,\alpha,p$, the bound is a constant times $\delta^{(\alpha+1)/(\alpha+p)}$. If the displayed minimizer exceeds 1, the theorem still applies: choose $t=1$, or take the infimum over all $0<t\leq1$. When $p=1$, the bound is $Ct^{\alpha+1}+2\delta$; letting $t$ decrease to zero yields a bound of $2\delta$, since $\alpha>0$.

Worked Example: Optimizing a Squared-Error Bound

Suppose $\alpha=1$, $C=2$, $p=2$, and $\delta=0.01$. The threshold is

t_*=\left(\frac{2^2(2-1)(0.01)}{2(1+1)}\right)^{1/3} =(0.01)^{1/3}\approx0.215443.

This threshold is within $(0,1]$. The first term is $2t_*^2\approx2(0.0464159)=0.0928318$. The second is $4(0.01)t_*^{-1}=0.04/0.215443\approx0.1856636$. Thus the optimized bound is approximately $0.0928318+0.1856636=0.2784954$, or $0.2785$ to four decimal places. These terms need not be equal: at the optimum their ratio is determined by the exponents in the two powers of $t$.

Worked Example: Applying Markov's Inequality to a Random Fit

Let $X$ be constant, with $\eta(X)=0.6$, so $\Delta(X)=0.2$. Suppose the estimator equals $0.4$ with probability $0.1$ over training samples and $0.6$ with probability $0.9$. In the first case the classifier predicts class 0 and disagrees with the Bayes rule; otherwise it predicts class 1. The expected regret is $0.1(0.2)=0.02$, and the expected squared regression error is $\delta=0.1(0.2)^2=0.004$.

For $t=0.1$, the margin probability is zero, so the margin condition holds, for example, with $\alpha=1$ and $C=5$. Markov's inequality bounds the probability of disagreement by $4\delta/(0.2)^2=0.016/0.04=0.4$. Multiplying by the margin gives a regret bound of $0.2(0.4)=0.08$, which agrees with the theorem's high-margin term $4(0.004)(0.1)^{-1}=0.16$ only after noting that the theorem uses the weaker threshold $t$, not the pointwise margin $0.2$. Both are valid bounds; the pointwise calculation is sharper here. The theorem's full bound is $0+0.16$, still above the exact regret $0.02$.

Interpretation and a Common Pitfall

The exponent $(\alpha+1)/(\alpha+p)$ records how the margin distribution and regression error work together. A larger $\alpha$ means less probability is concentrated close to the decision threshold, so errors are less likely to cause consequential disagreements. The bound is an upper guarantee, not an exact prediction of regret: as the examples show, Markov's inequality and a single global threshold can make it conservative.

Pitfall: claiming regret is bounded directly by regression error. An $L_p$ error bound alone does not say where the error occurs relative to the threshold. The correction is to separate small-margin points from large-margin points and use the margin condition for the former.
Pitfall: omitting the factor of two. With $\Delta=|2\eta-1|$, disagreement requires error at least $\Delta/2$, producing the factor $2^p$ in Markov's inequality. Using the alternative margin $|\eta-1/2|$ changes these constants.
Pitfall: treating a bound as an equality. The theorem supplies an upper bound. Its optimized value need not match actual regret, and its two terms are not generally equal at the optimum.

Key takeaway: Under a margin condition, an expected p-th-power regression error $\delta$ implies a plug-in regret bound of order $\delta^{(\alpha+1)/(\alpha+p)}$ when $p>1$ and the optimizing threshold lies in the allowed range. The conversion follows by balancing small-margin regret against Markov control of large-margin disagreements.

Check Your Understanding

Use the definitions and derivation above to answer the following questions.

Why does disagreement between the plug-in and Bayes classifiers imply regression error at least $\Delta(X)/2$?
Which term in the regret bound controls features with margin at most $t$, and where does the exponent $\alpha+1$ come from?
For $p=2$, what factor multiplies $\delta t^{-1}$, and why?
How does the optimizing threshold depend on $\delta$, $C$, $\alpha$, and $p$ when $p>1$?
Why can the theorem's bound be substantially larger than the exact regret in a particular example?