A Gaussian-Kernel Rate Calculation Under a Margin Condition

From Boundary Approximation to Excess Risk

A rate calculation for a kernel classifier connects three different quantities: how well the Bayes decision boundary can be approximated, how costly it is to estimate a score from data, and how much probability lies near the boundary. A margin condition controls the last quantity. When there is little probability near the boundary, a score estimate need not be extremely accurate everywhere to give a good classification rule.

The calculation below is deliberately conditional on stated bounds. Gaussian kernels alone do not imply one universal rate: the rate depends on the approximation and complexity properties available for the data distribution, the score, and the chosen bandwidth. We make those inputs explicit, derive the margin conversion, and then optimize the penalty and bandwidth.

The score \(g^*\) is the conditional mean of \(Y\). Its sign determines the Bayes decision, while its magnitude \(|g^*(x)|\) measures how far the conditional label probability is from one half. For a measurable score \(f\), the excess risk has the identity

Indeed, conditionally on \(X=x\), predicting the less likely label costs \(|2\eta(x)-1|\) more than predicting the more likely label. The identity follows by averaging this conditional difference. Points with \(g^*(x)=0\) contribute zero excess risk regardless of the tie convention.

The Assumptions for the Rate Calculation

Use a Gaussian kernel with bandwidth \(h\), denoted \(K_h(x,x')=\exp(-\|x-x'\|^2/(2h^2))\), and let \(\mathcal H_h\) be its reproducing-kernel Hilbert space. Consider a score estimator \(\hat f_{h,\lambda}\) using penalty \(\lambda>0\), classified by its sign. The rate calculation uses the following inputs; they should be checked for the setting at hand rather than inferred just from the word “Gaussian.”

• Boundary approximation: for each sufficiently small \(h>0\), there is a score \(f_h\in\mathcal H_h\) such that \(E[(f_h(X)-g^*(X))^2]\leq A h^{2s}\) and \(\|f_h\|_{\mathcal H_h}^2\leq C h^{-2r}\), for constants \(A,C>0\), \(s>0\), and \(r\geq0\).
• Complexity and penalty bound: for constants \(B,D>0\), the estimator satisfies \(E[(\hat f_{h,\lambda}(X)-g^*(X))^2]\leq A h^{2s}+B\lambda h^{-2r}+D h^{-d}/(n\lambda)\), where \(d>0\) and the expectation includes the training sample and a new feature vector.
• Margin condition: for some \(q\geq0\) and \(M>0\), \(P(|g^*(X)|\leq t)\leq M t^q\) for \(0<t\leq1\). When \(q=0\), this is simply a bounded-probability condition and gives no additional decay near the boundary.

The second condition is an assumed oracle-style score-error bound combining the approximation, penalty, and estimation contributions. Its particular complexity term is part of the premise of this calculation; other valid bounds can lead to different penalty choices and rates. The result below also assumes that the displayed bound applies over the bandwidth and penalty choices being considered.

Margin Condition Converts Score Error to Classification Risk

The key conversion does not require the estimator to have the correct sign everywhere. Instead, it bounds the risk from sign mistakes by separating points close to the Bayes boundary from points farther away. The margin condition makes the first group small, and a small squared score error limits the second group.

To prove the claim, take \(0<t\leq1\). On the event \(\{|g^*(X)|\leq t\}\), the excess-risk integrand is at most \(t\). On a disagreement event with \(|g^*(X)|>t\), the scores \(f(X)\) and \(g^*(X)\) have opposite decisions, so \(|f(X)-g^*(X)|\geq|g^*(X)|\). Therefore \(|g^*(X)|\leq(f(X)-g^*(X))^2/t\) on that event. Combining the two parts gives

If \(0<\Delta\leq1\), choose \(t=\Delta^{1/(q+2)}\), which lies in \((0,1]\). Both terms on the right are then bounded by a constant times \(\Delta^{(q+1)/(q+2)}\). If \(\Delta=0\), \(f=g^*\) almost surely and the excess risk is zero. If \(\Delta>1\), excess risk is at most one, which is also at most \(\Delta^{(q+1)/(q+2)}\). Enlarging the constant if needed proves the result in all cases. \(\square\)

For a random estimator, apply this inequality conditionally on the fitted score and then average over the training sample. Since \(\kappa=(q+1)/(q+2)\) lies in \((0,1)\), Jensen’s inequality for the concave function \(u^\kappa\) yields

Optimize the Penalty at a Fixed Bandwidth

For fixed \(h\), the two terms involving \(\lambda\) move in opposite directions. The penalty contribution grows with \(\lambda\), while the assumed complexity contribution shrinks with \(\lambda\). Balance them by setting their values equal:

Solving this positive equation gives the penalty choice

This is the minimizer of the sum of those two terms: for positive \(u,v\), \(u\lambda+v/\lambda\) is at least \(2\sqrt{uv}\), with equality at \(\lambda=\sqrt{v/u}\). Here \(u=Bh^{-2r}\) and \(v=Dh^{-d}/n\). Substitution gives the optimized score-error bound

The optimal penalty can increase or decrease with \(h\), depending on \(r-d/2\). It is therefore not generally correct to treat the penalty as a constant when selecting the bandwidth.

Optimize the Bandwidth and Obtain the Rate

Write \(u=r+d/2\), which is positive under the stated \(d>0\), \(r\geq0\) assumptions. After optimizing \(\lambda\), the bandwidth-dependent score-error bound has the form \(A h^{2s}+K n^{-1/2}h^{-u}\), where \(K=2\sqrt{BD}\). The first term increases with \(h\), while the second decreases with it. Balance their orders:

At this bandwidth, both score-error terms have order \(n^{-2s/(4s+2u)}\). Applying the margin conversion gives the excess-risk rate

Here \(\lesssim\) hides constants independent of \(n\). The display is an asymptotic rate under the three stated inputs, not a universal guarantee for every Gaussian-kernel classifier. In particular, the margin condition changes the exponent through \((q+1)/(q+2)\), while approximation smoothness and complexity affect the exponent through \(s,r,d\).

Common Pitfall and Practical Interpretation

A common mistake is to claim that a strong margin condition automatically makes the estimator’s score error decay faster. The margin condition does not change the assumed approximation or complexity bound. It changes how that score error translates into classification risk. In this calculation, the score-error rate is first derived from the two balanced terms; only then is it raised to the power \((q+1)/(q+2)\).

A second mistake is to optimize only the bandwidth, treating \(\lambda\) as fixed, or to optimize only the penalty while ignoring how the complexity term depends on \(h\). The valid sequence here is to balance the two \(\lambda\)-dependent terms at each bandwidth, substitute the resulting \(\lambda_*(h)\), and then balance the remaining approximation and estimation terms. The steps rely on the stated bounds and on admissible choices: if \(\lambda_*(h)\) falls outside the range where the bound holds, the calculation must be modified.

The practical value of this calculation is diagnostic as well as predictive. It shows exactly which assumptions support a proposed rate and where a slower rate may arise: weak boundary approximation, an expensive complexity term, or substantial probability near the Bayes boundary. Different approximation or complexity bounds should be inserted into the same margin argument and optimized on their own terms.