Deriving the Smoothness–Noise Rate by Scale Balancing

Why Two Scales Determine the Classification Rate

A classifier can make mistakes only where its estimated regression function points to the wrong side of one half. Its excess risk is therefore governed by two quantities: how accurately the regression function is estimated, and how much probability lies near the decision boundary, where even a small estimation error can change the predicted class. Smoothness controls the first quantity; a margin condition controls the second.

The aim here is to derive the resulting rate by choosing a spatial bandwidth that balances local bias against sampling variability. The derivation concerns plug-in classification: estimate the conditional class probability, then classify according to whether that estimate is above or below one half.

From Regression Error to Classification Regret

The margin is twice the distance from \(\eta(x)\) to the decision threshold. Thus, if an estimated regression function \(\hat\eta(x)\) differs from \(\eta(x)\) by less than \(M(x)/2\), it cannot cross the threshold and reverse the Bayes decision. This observation gives the basic link between regression estimation and classification.

To verify the identity, condition on \(X=x\). Predicting 1 has conditional error \(1-\eta(x)\); predicting 0 has conditional error \(\eta(x)\). The smaller of these is the Bayes conditional risk. Choosing the other decision increases conditional risk by \(|(1-\eta(x))-\eta(x)|=|2\eta(x)-1|\). Averaging over \(X\) proves the identity.

The margin condition limits the probability of points with small \(M(X)\). We use the convention $$ P(M(X)\le t)\le C t^\alpha,\qquad t>0, $$ for constants \(C>0\) and \(\alpha\ge 0\). A larger \(\alpha\) means less probability mass near the boundary. The condition is assumed over all positive \(t\); since \(M(X)\le1\), only thresholds up to one are substantively informative.

Local Regression Error at Bandwidth \(h\)

A local regression estimator averages observations in a neighborhood with spatial radius \(h\), or uses local polynomial fitting with comparable effective volume. Under a density bounded away from zero and infinity on the relevant design region, that neighborhood contains on the order of \(nh^d\) observations. Its standard deviation is therefore on the order of \((nh^d)^{-1/2}\). If \(\eta\) is Hölder smooth of order \(\beta>0\), the local approximation bias is on the order of \(h^\beta\).

For a precise rate statement, the following argument uses a pointwise concentration condition. It is satisfied by appropriate local estimators under standard design, bounded-response, and smoothness conditions; boundary handling and estimator construction must be chosen so that the stated bias and concentration bounds hold.

Set \(s_h=(nh^d)^{-1/2}\), the stochastic error scale. The assumption says that error beyond a bias allowance \(Bh^\beta\) has a tail that decays on scale \(s_h\). The next result shows how this pointwise control combines with the margin condition.

Proof. By the excess-risk identity, the expected regret is the expectation of \(M(X)\) times the indicator of a classification disagreement, also averaging over the training sample. First consider \(M(X)\le q_h\). The contribution from this event is at most $$ q_h P(M(X)\le q_h)\le Cq_h^{1+\alpha}. $$ Now divide \(M(X)>q_h\) into shells \(2^kq_h<M(X)\le2^{k+1}q_h\), for integers \(k\ge0\). On shell \(k\), disagreement requires estimation error at least \(M(X)/2\), hence at least \(2^{k-1}q_h\). Since \(q_h\ge4Bh^\beta\), this threshold exceeds the bias allowance by at least a fixed positive multiple of \(2^kq_h\). The concentration assumption therefore bounds the conditional disagreement probability on this shell by \(2\exp(-c_1 4^kq_h^2/s_h^2)\) for a constant \(c_1>0\). Also \(q_h\ge s_h\), so this is at most \(2\exp(-c_1 4^k)\).

The regret on the shell is at most \(2^{k+1}q_h\). Its probability is at most \(P(M(X)\le2^{k+1}q_h)\le C(2^{k+1}q_h)^\alpha\). Thus the sum of the shell contributions is bounded by a constant times $$ q_h^{1+\alpha}\sum_{k=0}^{\infty}2^{k(1+\alpha)}\exp(-c_1 4^k). $$ This series is finite: its exponential factor decreases faster than its geometric factor grows. Adding the small-margin contribution proves the result. \(\square\)

Balancing Bias and Sampling Variability

The theorem reduces the rate calculation to selecting \(h\). A smaller bandwidth reduces the smoothness bias \(h^\beta\), but leaves fewer observations in each neighborhood and increases \((nh^d)^{-1/2}\). The natural balance sets these two scales equal.

The exponent has a direct interpretation. Greater smoothness \(\beta\) makes local approximation more accurate as \(h\) shrinks. Larger dimension \(d\) makes neighborhoods sparse more quickly, slowing the rate. A larger margin exponent \(\alpha\) reduces the mass of points whose labels are vulnerable to small regression errors, improving the classification rate.

A Direct Margin Bound and a Common Pitfall

A simpler deterministic argument is useful when a uniform regression-error guarantee is available. If \(|\hat\eta(x)-\eta(x)|\le r\) for every relevant \(x\), then disagreement is possible only when \(M(x)\le2r\). On that set the regret contribution per point is at most \(2r\), so $$ R(g_{\hat\eta})-R(g^*)\le 2rP(M(X)\le2r)\le 2Cr^{1+\alpha}. $$ This proves the same conversion from regression accuracy to classification regret, but a uniform error bound can be more demanding than the pointwise control used above.

A common mistake is to use a uniform regression bound and then report the scale-free rate without checking whether that bound contains a logarithm. For instance, a uniform concentration argument often yields an error scale involving \(\sqrt{\log n/(nh^d)}\), rather than \((nh^d)^{-1/2}\). Balancing with that term can introduce a logarithmic factor. That is not an algebra error: it reflects the stronger uniform guarantee used in the argument. The pointwise concentration derivation above explains how integrating over the covariate distribution can avoid paying for uniform control at every \(x\).