From Uniform Regression Deviation to Finite-Sample Risk

From Regression Accuracy to Classification Risk

A plug-in classifier estimates the conditional probability of class 1 and assigns a label according to whether that estimate is above one half. A uniform bound on the estimation error is especially useful: it controls the estimate at every feature value simultaneously. To turn that control into a risk guarantee, we need to know how much probability lies near the threshold. The margin condition supplies exactly this information.

The resulting guarantee is finite-sample and high-probability. On the event that the regression estimate is uniformly accurate to within $\varepsilon$, any classification disagreement with the Bayes rule must occur close to the Bayes threshold. A margin condition limits the probability of that region, and the excess-risk identity weights it by how costly a disagreement is.

Setup and Margin Condition

Definition: Let $(X,Y)$ have a joint distribution with $Y\in\{0,1\}$, and let $\eta(x)=P(Y=1\mid X=x)$ be a measurable version of the binary regression function. The Bayes classifier is $g^*(x)=\mathbf{1}\{\eta(x)\geq 1/2\}$. For an estimator $\hat{\eta}$, the plug-in classifier is $\hat{g}(x)=\mathbf{1}\{\hat{\eta}(x)\geq 1/2\}$. For any classifier $g$, its risk is $R(g)=P(g(X)\ne Y)$.

Write $D_n$ for the data used to construct $\hat{\eta}$. The risk $R(\hat{g})$, conditional on $D_n$, means the probability of error on a fresh pair $(X,Y)$ from the target distribution, with the fitted classifier held fixed. The excess risk is $R(\hat{g})-R(g^*)$.

Definition: The margin condition with constants $C_m>0$ and $\alpha\geq 0$ is $$ P\bigl(|\eta(X)-1/2|\leq t\bigr)\leq C_m t^\alpha \qquad\text{for every }t>0. $$ It controls the probability mass near the classification threshold. Larger $\alpha$ means less mass can be concentrated close to that threshold.

The convention here uses distance $|\eta(X)-1/2|$, rather than twice that distance. Constants in bounds therefore depend on this choice of convention.

The Finite-Sample Transfer Result

Theorem: Suppose the margin condition holds with constants $C_m$ and $\alpha$. Suppose that, for a deterministic $\varepsilon>0$ and $0<\rho<1$, the regression estimator satisfies $$ P_{D_n}\left(\sup_{x\in\mathcal{X}}|\hat{\eta}(x)-\eta(x)|\leq\varepsilon\right)\geq 1-\rho, $$ where the supremum and event are measurable (or are understood on a measurable set of full probability). Then $$ P_{D_n}\left(R(\hat{g})-R(g^*)\leq \min\{1,\;2C_m\varepsilon^{\alpha+1}\}\right)\geq 1-\rho. $$

Here $\mathcal{X}$ is the feature space on which the uniform guarantee is asserted. The result applies to any procedure satisfying the displayed guarantee; it does not require a particular way of estimating $\eta$.

Proof. For a fixed classifier $g$, conditional on $X=x$, predicting 0 has error probability $\eta(x)$, while predicting 1 has error probability $1-\eta(x)$. The Bayes rule chooses the smaller of these two quantities. Therefore, if $g(x)\ne g^*(x)$, its conditional risk exceeds the Bayes conditional risk by $|2\eta(x)-1|$; if the classifiers agree, the difference is zero. Integrating over $X$ gives the exact excess-risk identity

R(g)-R(g^*)=E\left[|2\eta(X)-1|\,\mathbf{1}\{g(X)\ne g^*(X)\}\right].

Now consider any data set in the event $\sup_x|\hat{\eta}(x)-\eta(x)|\leq\varepsilon$. If $\hat{g}(x)\ne g^*(x)$, then the two values $\eta(x)$ and $\hat{\eta}(x)$ lie on opposite sides of the threshold, allowing equality at the threshold under the stated tie convention. It follows that $|\eta(x)-1/2|\leq\varepsilon$. Also, on this disagreement set, $|2\eta(x)-1|\leq 2\varepsilon$. The identity consequently gives

\begin{aligned} R(\hat{g})-R(g^*) &\leq 2\varepsilon\,P\bigl(|\eta(X)-1/2|\leq\varepsilon\bigr)\\ &\leq 2C_m\varepsilon^{\alpha+1}. \end{aligned}

An excess risk is also at most 1, since each risk lies in $[0,1]$. Thus the stated minimum is a valid bound on the same event. The uniform-error event has probability at least $1-\rho$ over $D_n$, so the risk bound has at least that probability as well. $\square$

Worked Conversions

Worked Example: A Discrete Feature Distribution

Suppose $X$ takes three values $a,b,c$, with probabilities $0.4,0.4,0.2$, respectively. Let $\eta(a)=0.20$, $\eta(b)=0.45$, and $\eta(c)=0.80$. The distances from the threshold are $0.30,0.05,0.30$. For $0<t<0.05$, the margin probability is zero. For $0.05\leq t<0.30$, it is $0.4$; for $t\geq0.30$, it is 1. Hence the margin condition holds with $\alpha=1$ and $C_m=8$: on the middle range, $0.4\leq8t$, and on the final range, $1\leq8t$.

Suppose a fitted regression function has a uniform error at most $\varepsilon=0.04$ with probability at least $0.95$. Since all three threshold distances exceed $0.04$, the plug-in classifier agrees with the Bayes classifier at every feature value on this event. In particular, the excess risk is zero there. The general theorem gives the valid, though looser, bound

2C_m\varepsilon^{\alpha+1} =2(8)(0.04)^2 =16(0.0016) =0.0256.

Thus the theorem guarantees excess risk at most $0.0256$ with probability at least $0.95$; the discrete model lets us verify the stronger conclusion of zero excess risk on the same event.

Worked Example: A Continuous Model with Linear Margin Behavior

Let $X$ be uniform on $[0,1]$ and let $\eta(x)=x$. Then $|\eta(X)-1/2|=|X-1/2|$. For $0<t\leq1/2$, the set of feature values within distance $t$ of $1/2$ is an interval of length $2t$, so its probability is $2t$. For $t>1/2$, that probability is 1, which is also at most $2t$. Thus the margin condition holds with $\alpha=1$ and $C_m=2$.

Suppose that at sample size $n=400$, an estimator satisfies $P_{D_n}(\sup_x|\hat{\eta}(x)-\eta(x)|\leq0.10)\geq0.99$. The risk bound on this event is

2C_m\varepsilon^{\alpha+1} =2(2)(0.10)^2 =4(0.01) =0.04.

Consequently, the excess risk is at most $0.04$ with probability at least $0.99$ over the training data. The sample size alone does not establish this result: the stated uniform-error guarantee is an input to the conversion.

Worked Example: A Stronger Margin Exponent

Let $X$ have density $f_X(x)=8x$ on $0\leq x\leq1/2$, and set $\eta(x)=1/2+x$. The density integrates to one because $\int_0^{1/2}8x\,dx=1$. For $0<t\leq1/2$,

P(|\eta(X)-1/2|\leq t)=\int_0^t 8x\,dx=4t^2.

For $t>1/2$, the probability is 1 and $1\leq4t^2$. Thus the margin condition holds for all $t>0$ with $\alpha=2$ and $C_m=4$. If a regression estimator has uniform error at most $0.10$ with probability at least $0.97$, the theorem yields

2C_m\varepsilon^{\alpha+1} =2(4)(0.10)^3 =8(0.001) =0.008.

The excess risk is therefore at most $0.008$ with probability at least $0.97$. Compared with a margin exponent of 1, the exponent 2 makes the bound decrease as the cube of the uniform error rather than its square.

What the Bound Says About Rates

The conversion keeps the probability level of the regression guarantee and raises the error tolerance to the power $\alpha+1$. For example, if a sequence of estimators satisfies

P_{D_n}\left(\sup_x|\hat{\eta}(x)-\eta(x)|\leq\varepsilon_n\right)\geq1-\rho_n,

then, under the same margin condition,

P_{D_n}\left(R(\hat{g})-R(g^*)\leq \min\{1,2C_m\varepsilon_n^{\alpha+1}\}\right)\geq1-\rho_n.

This is a direct finite-sample implication, not an asymptotic statement. Any rate for $\varepsilon_n$ can be substituted into the right-hand side, but the bound is only as strong as the uniform-error guarantee and the margin condition actually available.

A useful way to remember the two powers is to separate the two effects. Disagreement can occur only in a threshold band of width $\varepsilon$, whose probability is at most $C_m\varepsilon^\alpha$. At every point in that band, the excess conditional risk is at most $2\varepsilon$. Multiplying these controls produces $2C_m\varepsilon^{\alpha+1}$.

Common Mistake

Wrong reasoning: A uniform error of $\varepsilon$ means the excess risk is at most $\varepsilon$. This treats regression error and classification regret as if they were the same quantity.
Correction: First localize possible classification disagreements to $|\eta(X)-1/2|\leq\varepsilon$. Then use the margin condition to control the probability of that set and the excess-risk identity to control the cost of a disagreement. The resulting bound is $2C_m\varepsilon^{\alpha+1}$, capped at 1.
Important qualification: Without a margin condition, the probability of a narrow threshold band may be large. Uniform regression accuracy still localizes disagreement, but it does not by itself guarantee the additional power $\alpha$ in the risk bound.

Key takeaway: A high-probability uniform regression bound transfers to a high-probability classification-risk bound by combining disagreement localization with the margin condition. The probability level is unchanged, while the risk tolerance scales as the uniform error raised to $\alpha+1$.

Check Your Understanding

Use the threshold-localization argument and the theorem to answer these questions.

If $\alpha=1$, $C_m=3$, and $\varepsilon=0.05$, what excess-risk bound does the theorem give?
Why does the theorem retain the same probability $1-\rho$ as the uniform-error guarantee?
For $\alpha=2$, how does the risk bound change when the uniform error is multiplied by one half?
What can be concluded from a uniform error bound if no margin condition is assumed?
In the continuous example with $X$ uniform on $[0,1]$ and $\eta(x)=x$, verify the margin probability for $t=0.2$.