Worked Conversion of Nonparametric Regression Rates

From Regression Error to Classification Regret

A plug-in classifier first estimates the conditional probability of class 1 and then assigns a label according to whether that estimate is above one half. Regression error alone does not determine how often this rule makes consequential mistakes: errors far from the classification threshold are more likely to change the label than errors of the same size near it. A margin condition quantifies how much probability lies close to that threshold. This tutorial works through the algebra that combines a regression-error rate with a margin exponent to give a classification-regret rate.

Let $Y\in\{0,1\}$, let $X$ be the feature vector, and define $\eta(x)=P(Y=1\mid X=x)$. For a measurable function $g$ taking values in $[0,1]$, the plug-in rule is $\hat h_g(x)=\mathbf{1}\{g(x)\ge 1/2\}$. A Bayes rule is $h^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$; either choice at a tie is optimal. Write $D(x)=|2\eta(x)-1|$ for the distance from the Bayes threshold on the doubled probability scale.

Definition: A distribution satisfies a margin condition with exponent $\alpha\ge 0$ and constant $C_m>0$ if $$ P_X\bigl(D(X)\le t\bigr)\le C_m t^\alpha,\qquad 0<t\le 1. $$ Here $P_X$ is the marginal distribution of $X$. The convention uses $D=|2\eta-1|$; using $|\eta-1/2|$ instead changes constants but not the exponent.

The classification regret of a rule $h$ is $R(h)-R(h^*)$, where $R(h)=P(h(X)\ne Y)$. Conditional on $X=x$, choosing the less likely label incurs excess error $D(x)$. Consequently,

R(\hat h_g)-R(h^*)= E\!\left[D(X)\mathbf{1}\{\hat h_g(X)\ne h^*(X)\}\right].

We use this identity to translate deviations of $g$ from $\eta$ into regret. For a data-dependent estimate, the arguments below apply conditionally on its training data when the stated error bound holds conditionally. For an integrated bound in expectation, the test observation must be independent of the training data; averaging the conditional inequality then gives the corresponding unconditional bound.

Uniform Error: A Direct Conversion

Suppose the estimate is uniformly within $\delta$ of the regression function. If the plug-in label differs from the Bayes label at $x$, the estimated probability must have crossed the threshold relative to the true probability. In particular, $|g(x)-\eta(x)|\ge |\eta(x)-1/2|=D(x)/2$. Thus disagreement can occur only where $D(x)\le 2\delta$.

Theorem: If $\sup_x|g(x)-\eta(x)|\le\delta$ and $0<2\delta\le1$, then under the margin condition, $$ R(\hat h_g)-R(h^*)\le C_m\,2^{\alpha+1}\delta^{\alpha+1}. $$ For $\delta=0$, the regret is zero.

Proof. When $\hat h_g(x)\ne h^*(x)$, the threshold-crossing inequality gives $D(x)\le 2|g(x)-\eta(x)|\le 2\delta$. Use the regret identity and then the margin condition:

\begin{aligned} R(\hat h_g)-R(h^*) &=E\!\left[D(X)\mathbf{1}\{\hat h_g(X)\ne h^*(X)\}\right]\\ &\le E\!\left[D(X)\mathbf{1}\{D(X)\le 2\delta\}\right]\\ &\le 2\delta\,P_X(D(X)\le 2\delta)\\ &\le 2\delta\,C_m(2\delta)^\alpha =C_m2^{\alpha+1}\delta^{\alpha+1}. \end{aligned}

If $\delta=0$, then $g=\eta$ everywhere in the stated uniform bound, so the plug-in and Bayes rules agree apart from irrelevant choices at ties and have zero regret. This proves the claim. $\square$

Worked Example: A Uniform Rate with Linear Margin Behavior

Suppose $\alpha=1$, the margin constant is $C_m$, and a regression estimate satisfies $\sup_x|g_n(x)-\eta(x)|\le n^{-1/3}$. Convert this into a regret bound.

Here $2\delta_n=2n^{-1/3}$, which is at most 1 for $n\ge 8$. The theorem gives

R(\hat h_{g_n})-R(h^*) \le C_m2^{1+1}(n^{-1/3})^{1+1} =4C_m n^{-2/3},\qquad n\ge8.

The classification rate has exponent $2/3$ in $n$, rather than the regression exponent $1/3$, because the uniform deviation is raised to the power $1+\alpha=2$. The bound is conditional if the assumed uniform inequality holds conditionally on the training data.

Integrated Error: The Lp Conversion

Uniform control can be stronger than the regression result available from an estimator. An alternative is to control its integrated $p$th-power error under the feature distribution. The margin condition still helps, but the argument must account for the possibility that large regression errors occur on a small set. The splitting-at-a-margin-level argument does this: points with small $D$ are controlled by their probability mass, while points with larger $D$ require a correspondingly larger regression error to cause disagreement.

Theorem: Let $p\ge1$, and suppose $$ Q=E\!\left[|g(X)-\eta(X)|^p\right]\le1. $$ Under the margin condition, if $Q>0$, then $$ R(\hat h_g)-R(h^*)\le (C_m+2^p)\, Q^{(\alpha+1)/(p+\alpha)}. $$ If $Q=0$, the regret is zero.

Proof. First take any $t$ with $0<t\le1$. Split the regret according to whether $D(X)\le t$ or $D(X)>t$. On the first part, $D\le t$, so its contribution is at most $tP_X(D\le t)\le C_m t^{\alpha+1}$. On the second part, disagreement implies $|g(X)-\eta(X)|\ge D(X)/2$. Since $p\ge1$, on that part,

D(X) \le 2^p|g(X)-\eta(X)|^pD(X)^{1-p} \le 2^p|g(X)-\eta(X)|^p t^{1-p}.

The first inequality follows by raising $|g-\eta|\ge D/2$ to the $p$th power and rearranging. The second follows because $D>t$ and $1-p\le0$, so $D^{1-p}\le t^{1-p}$. Combining the two parts gives, for every such $t$,

R(\hat h_g)-R(h^*)\le C_m t^{\alpha+1}+2^p Q\,t^{1-p}.

If $Q>0$, choose $t=Q^{1/(p+\alpha)}$. The assumption $Q\le1$ ensures $0<t\le1$. Both terms then have the same power of $Q$:

\begin{aligned} t^{\alpha+1} &=Q^{(\alpha+1)/(p+\alpha)},\\ Q\,t^{1-p} &=Q\left(Q^{1/(p+\alpha)}\right)^{1-p} =Q^{1+(1-p)/(p+\alpha)} =Q^{(\alpha+1)/(p+\alpha)}. \end{aligned}

Therefore the claimed bound follows. If $Q=0$, the nonnegative random variable $|g(X)-\eta(X)|^p$ has expectation zero, so it is zero $P_X$-almost surely. The plug-in rule then agrees with the Bayes rule $P_X$-almost surely, giving zero regret. This also covers the case excluded by the positive choice of $t$. $\square$

Often a regression result is stated as an $L_p(P_X)$ norm bound rather than a moment bound. If $\|g-\eta\|_{L_p(P_X)}\le r$, then $Q\le r^p$. Substitution yields the rate in terms of the norm:

R(\hat h_g)-R(h^*)\le (C_m+2^p)\,r^{p(\alpha+1)/(p+\alpha)} \qquad (r^p\le1).

The factor $p$ in the exponent is essential: a rate for the norm is not a rate for its $p$th moment. If $r_n$ is proportional to $n^{-\gamma}$, this conversion gives a regret rate proportional to $n^{-\gamma p(\alpha+1)/(p+\alpha)}$, subject to the stated bounds and constants.

Worked Example: An Integrated L2 Rate

Suppose $\alpha=1$, $p=2$, and $\|g_n-\eta\|_{L_2(P_X)}\le 2n^{-1/5}$. Find the resulting regret rate and check when the moment condition $Q\le1$ holds.

Squaring the norm bound gives $Q\le4n^{-2/5}$. This is at most 1 when $n^{2/5}\ge4$, equivalently $n\ge4^{5/2}=32$. The exponent in the theorem is $(\alpha+1)/(p+\alpha)=2/3$. Hence, for $n\ge32$,

\begin{aligned} R(\hat h_{g_n})-R(h^*) &\le (C_m+2^2)(4n^{-2/5})^{2/3}\\ &=(C_m+4)\,4^{2/3}n^{-4/15}. \end{aligned}

Equivalently, using the norm directly, the exponent is $p(\alpha+1)/(p+\alpha)=4/3$, and $(2n^{-1/5})^{4/3}=4^{2/3}n^{-4/15}$. The two calculations agree.

Worked Example: An Integrated L1 Rate with a Larger Margin Exponent

Suppose $\alpha=2$, $p=1$, and $E[|g_n(X)-\eta(X)|]\le3n^{-1/4}$. Determine the regret rate and the sample-size condition for applying the theorem.

Now $Q=3n^{-1/4}$, which is at most 1 for $n\ge3^4=81$. The conversion exponent is

\frac{\alpha+1}{p+\alpha}=\frac{3}{3}=1.

Since $2^p=2$, the bound is

R(\hat h_{g_n})-R(h^*) \le(C_m+2)Q \le3(C_m+2)n^{-1/4},\qquad n\ge81.

For this choice of $p$ and $\alpha$, the regret rate has the same sample-size exponent as the integrated absolute-error rate. The margin condition affects the constant and the derivation, but this particular exponent calculation produces no further power improvement.

Worked Example: Substituting a Nonparametric Uniform Rate

Suppose a uniform regression bound is $\delta_n=(\log n/n)^{1/4}$, and assume a margin exponent $\alpha=1$. For sample sizes satisfying $\log n/n\le1/16$, we have $\delta_n\le1/2$, so the uniform conversion applies. It gives

R(\hat h_{g_n})-R(h^*) \le4C_m\delta_n^2 =4C_m\left(\frac{\log n}{n}\right)^{1/2}.

The logarithmic factor is also squared: $\delta_n^2=(\log n/n)^{1/2}$. This is an algebraic consequence of the uniform-error exponent $1+\alpha=2$, not a separate assumption about the classifier.

Reading the Exponents and Avoiding Pitfalls

The conversion formula records two different effects. The margin exponent controls how quickly the mass near the decision threshold decreases; the error norm determines how strongly rare large regression errors are penalized. For an integrated $p$th moment $Q_n$, the regret exponent is $(1+\alpha)/(p+\alpha)$. For an $L_p$ norm rate $r_n$, it is $p(1+\alpha)/(p+\alpha)$. For a uniform rate $\delta_n$, it is $1+\alpha$. These are different formulas because they start from different measures of regression error.

A common mistake is to insert an $L_2$ norm rate directly as $Q_n$ in the integrated theorem. If the norm is $r_n$, the relevant moment is $Q_n=r_n^2$, not $r_n$. For example, an $L_2$ rate $r_n=n^{-\gamma}$ with $\alpha=1$ gives a regret exponent $2\gamma\cdot2/3=4\gamma/3$, not $2\gamma/3$. Another mistake is to confuse the margin variables $D=|2\eta-1|$ and $|\eta-1/2|$. They differ by a factor of two, so constants in a bound change, but the margin exponent and resulting sample-size exponent do not.

Finally, check the range of the tuning level in the integrated proof. The chosen $t=Q^{1/(p+\alpha)}$ is valid because the theorem assumes $Q\le1$; when $Q=0$, it must be treated separately rather than substituted into a proof requiring $t>0$. These checks keep the stated result valid at both endpoints and make the rate conversion transparent.

Key takeaway: First identify whether the regression guarantee is uniform, an $L_p$ norm, or a $p$th-moment bound. Then apply the matching conversion: uniform error $\delta$ gives a $\delta^{1+\alpha}$ bound, while moment error $Q$ gives a $Q^{(1+\alpha)/(p+\alpha)}$ bound, under the stated margin condition.

Check Your Understanding

For each question, keep track of whether the stated error rate is a norm or a moment.

Under a margin exponent of 2, what power of a uniform error bound appears in the regret bound?
If an $L_2$ norm is bounded by $n^{-1/6}$ and the margin exponent is 1, what sample-size exponent follows for regret?
In the integrated proof, why is $D^{1-p}\le t^{1-p}$ on the part where $D>t$?
What conclusion follows when the integrated error moment $Q$ is zero?
How does switching from $|2\eta-1|$ to $|\eta-1/2|$ affect the rate exponent?