Shrinking Gaussian Bandwidths and Consistency Schedules

Why a Shrinking Bandwidth Needs a Schedule

A Gaussian kernel can resolve increasingly fine variation as its bandwidth shrinks. That flexibility can help approximate a complicated decision boundary, but it also changes the function space used by the classifier. In particular, the RKHS norm needed to represent a good classifier may grow as the bandwidth decreases. Regularization penalizes that norm, while the data must be numerous enough to estimate within the resulting class.

The relevant question is therefore not simply whether each Gaussian RKHS is rich. A consistency argument must coordinate three quantities: the bandwidth, the regularization level, and the sample size. The central sufficient conditions below make the approximation cost small, the penalty cost small, and the estimation error small at the same time.

Setup and a Risk Bound

Let $(X_i,Y_i)_{i=1}^n$ be independent observations from a common distribution, with $X_i$ in a compact set $\mathcal X\subset\mathbb R^d$ and $Y_i\in\{-1,+1\}$. For bandwidth $\sigma>0$, use the Gaussian kernel $k_\sigma(x,x')=\exp(-\|x-x'\|^2/(2\sigma^2))$, and let $\mathcal H_\sigma$ be its RKHS. Write $R(f)=P(\operatorname{sign}(f(X))\ne Y)$, and use the hinge loss $\phi(yf)=(1-yf)_+$, with population risk $R_\phi(f)=E[\phi(Yf(X))]$. Ties in the classifier may be assigned either label.

For a sample of size $n$, the regularized empirical classifier minimizes $P_n\phi(Yf(X))+\lambda\|f\|_{\mathcal H_\sigma}^2$ over $\mathcal H_\sigma$, where $P_n$ is the sample average and $\lambda>0$. The Gaussian kernel has $k_\sigma(x,x)=1$, so the reproducing property gives $|f(x)|\leq\|f\|_{\mathcal H_\sigma}$.

Definition: A sequence of classifiers is Bayes risk consistent if its classification risk converges to the Bayes risk $R^*=\inf_g P(g(X)\ne Y)$. For a data-dependent classifier, risk is evaluated on a fresh observation and is random through the training sample. Convergence in probability of its excess risk means $R(\hat f_n)-R^*\xrightarrow{p}0$.

Two standard facts connect the objective to consistency. First, the infimum hinge risk over measurable scores is $2R^*$. Indeed, if $\eta(x)=P(Y=1\mid X=x)$, the conditional hinge risk at score $t$ is $\eta(x)(1-t)_+ +(1-\eta(x))(1+t)_+$, whose minimum over $t\in\mathbb R$ is $2\min\{\eta(x),1-\eta(x)\}$. Second, for every score $f$, its classification excess risk is at most $R_\phi(f)-2R^*$. This follows conditionally: when the sign of $f(x)$ is wrong, the conditional hinge risk exceeds its minimum by at least $|2\eta(x)-1|$, the conditional classification excess; when the sign is correct, that classification excess is zero.

Theorem: Suppose $f\in\mathcal H_\sigma$ has $\|f\|_{\mathcal H_\sigma}\leq\lambda^{-1/2}$, and $\hat f$ minimizes the regularized empirical hinge objective for bandwidth $\sigma$ and penalty $\lambda$. Then $$ E\!\left[R_\phi(\hat f)\right] \leq R_\phi(f)+\lambda\|f\|_{\mathcal H_\sigma}^2+ \frac{8}{\sqrt{n\lambda}}. $$

Here the expectation is over the training sample. The numerical constant is a convenient bound, not a sharp one. The terms have distinct roles: the comparator's hinge risk is an approximation term, its squared norm incurs a regularization cost, and the last term controls estimation.

Why the Bound Holds

At an empirical minimizer, the objective is no larger than its value at the zero function, which is $1$. Since the empirical hinge loss is nonnegative, $\lambda\|\hat f\|_{\mathcal H_\sigma}^2\leq1$. Thus both $\hat f$ and the comparator in the theorem belong to the RKHS ball of radius $1/\sqrt{\lambda}$.

For completeness, the expected uniform deviation of hinge risks over that ball is at most $4/(\sqrt{n\lambda})$. Symmetrization bounds the expected supremum of absolute deviations by twice the expected Rademacher supremum of the loss class. The hinge loss is 1-Lipschitz as a function of the score, and the RKHS ball has Rademacher supremum at most $1/\sqrt{n\lambda}$: conditionally on the inputs, the reproducing property and Cauchy–Schwarz give $E_\epsilon\sup_{\|g\|\leq1/\sqrt\lambda}|n^{-1}\sum_i\epsilon_i g(X_i)|\leq1/\sqrt{n\lambda}$. The contraction inequality, with the standard absolute-supremum factor, yields the stated deviation bound.

On any sample, empirical minimization gives $P_n\phi(\hat f)+\lambda\|\hat f\|^2\leq P_n\phi(f)+\lambda\|f\|^2$. Add and subtract the population hinge risks of $\hat f$ and $f$. Their difference is at most the penalty $\lambda\|f\|^2$ plus twice the supremum deviation over the ball. Taking expectations and applying the deviation bound proves the theorem. $\square$

Joint Conditions and a Diagonal Schedule

For a changing bandwidth $\sigma_n$, the useful approximation quantity is not just the best hinge risk in $\mathcal H_{\sigma_n}$. It includes the norm cost of approximating a good score. A direct sufficient condition is that there are scores $f_n\in\mathcal H_{\sigma_n}$ for which

R_\phi(f_n)-2R^*\longrightarrow 0,\qquad \lambda_n\|f_n\|_{\mathcal H_{\sigma_n}}^2\longrightarrow 0,\qquad n\lambda_n\longrightarrow\infty.

The first condition makes the scores predictively adequate; the second ensures regularization does not prevent their use; the third makes the estimation bound vanish. Since the penalty condition implies $\lambda_n\|f_n\|^2\leq1$ eventually, the theorem applies for all sufficiently large $n$. Its bound then tends to zero. The classification excess risk is nonnegative and no larger than hinge excess risk, so Markov's inequality gives convergence in probability to zero.

These conditions can be met for every distribution in the setup, but generally not by asserting an arbitrary bandwidth and penalty sequence. On a compact set, each fixed-bandwidth Gaussian RKHS is dense in the continuous functions. Bounded measurable Bayes scores can be approximated in $L^1(P_X)$ by continuous scores, and the hinge loss is Lipschitz. Consequently, for each fixed positive bandwidth and each $j$, there is an RKHS score with hinge risk within $1/j$ of $2R^*$. Universality supplies such a score; it does not supply a useful bound on its norm as the bandwidth changes.

A diagonal construction makes the missing coordination explicit. Set $\sigma_j=1/j$. Choose $f_j\in\mathcal H_{\sigma_j}$ with $R_\phi(f_j)\leq2R^*+1/j$, and write $M_j=\|f_j\|_{\mathcal H_{\sigma_j}}$. Set $\lambda_j=1/[j(1+M_j^2)]$, and choose increasing integers $n_j$ with $n_j\geq j/\lambda_j$. For sample sizes $n_j\leq n<n_{j+1}$, use $\sigma_n=\sigma_j$ and $\lambda_n=\lambda_j$. As $n$ grows, the stage $j$ grows, so $\sigma_n\to0$ and $\lambda_n\to0$. Also,

\lambda_j M_j^2\leq \frac1j,\qquad n\lambda_j\geq n_j\lambda_j\geq j.

Thus the approximation, penalty, and estimation terms all vanish. This proves existence of a consistency schedule without claiming a universal rate or a practical way to select the schedule from data.

Worked Schedules

Worked Example: A Power-Law Schedule Under a Certified Bound

Suppose a problem-specific analysis has established an approximation bound of the form $C_1\sigma^2+C_2\lambda\sigma^{-4}$, where $C_1,C_2$ are fixed positive constants. This is an additional quantitative assumption, not a consequence of Gaussian universality alone. Try $\sigma_n=n^{-1/10}$ and $\lambda_n=n^{-3/5}$.

The bandwidth term is $\sigma_n^2=n^{-1/5}$. The regularization contribution involving bandwidth is $\lambda_n\sigma_n^{-4}=n^{-3/5}n^{4/10}=n^{-1/5}$. The estimation term has order $(n\lambda_n)^{-1/2}=(n^{2/5})^{-1/2}=n^{-1/5}$, since $n\lambda_n=n^{2/5}\to\infty$. All three vanish, so the supplied bound yields consistency. In exponent notation the requirements are $0<4a<b<1$, and here $a=1/10$, $b=3/5$ satisfy them.

Worked Example: An Explicit Diagonal Schedule on Two Points

Let $X$ be equally likely to be $-1$ or $+1$, and let $Y=X$. At stage $j$, take $\sigma_j=1/j$ and seek a Gaussian-RKHS score with values $(-1,+1)$ at $(-1,+1)$. The Gram matrix has diagonal entries 1 and off-diagonal entries $r_j=\exp(-2j^2)$. The squared RKHS norm of this interpolating score is $v^\mathsf{T}K^{-1}v$, where $v=(-1,+1)^\mathsf{T}$, giving

M_j^2=\frac{2}{1-r_j}=\frac{2}{1-\exp(-2j^2)}.

The score classifies both support points correctly and has hinge risk zero, which equals $2R^*$ because $R^*=0$. Choose $\lambda_j=1/[j(1+M_j^2)]$ and $n_j=\lceil j/\lambda_j\rceil$. Then $\lambda_jM_j^2\leq1/j$ and $n_j\lambda_j\geq j$, exactly as required. For $j=1$, $r_1\approx0.1353$, $M_1^2\approx2.313$, $\lambda_1\approx0.302$, and $n_1=4$; hence $n_1\lambda_1\approx1.21\geq1$. The same construction at later stages makes the two cost terms vanish.

Worked Example: Checking the Sample-Size Condition

Consider the estimation term alone. If $\lambda_n=1/n$, then $n\lambda_n=1$, and $(n\lambda_n)^{-1/2}=1$: this bound gives no vanishing estimation error. If instead $\lambda_n=n^{-1/2}$, then $n\lambda_n=n^{1/2}$ and the estimation term is $n^{-1/4}$, which does vanish.

This change does not by itself establish consistency. The penalty still has to shrink, and there must be good approximating scores whose norm cost satisfies $\lambda_n\|f_n\|^2\to0$. The calculation checks only the sample-size side of the joint conditions; it cannot substitute for the approximation and norm checks.

Why Fixed-Bandwidth Universality Is Not Enough

Universality is a density statement for each fixed kernel: every continuous target can be approximated in the corresponding RKHS, with no promise that the approximating function has a small norm. In a changing-bandwidth problem, the required norm can depend sharply on $\sigma_n$. If $\lambda_n$ is not small enough relative to that norm, the penalty can exclude the useful approximation. If $\lambda_n$ is made too small relative to $n$, the estimation term need not vanish.

Common mistake: “Every Gaussian kernel is universal, so letting the bandwidth shrink guarantees consistency.” This confuses a separate density result at each fixed bandwidth with a uniform approximation guarantee along a sequence. The correction is to exhibit approximating scores and check their norm costs, as well as $n\lambda_n\to\infty$. Without a quantitative approximation bound, the diagonal construction guarantees that a schedule exists, not that an arbitrary familiar power law works.

Key takeaway: A sufficient consistency schedule makes the approximating hinge risk approach $2R^*$, keeps $\lambda_n\|f_n\|_{\mathcal H_{\sigma_n}}^2$ small, and sends $n\lambda_n$ to infinity. Shrinking bandwidth is only one part of that joint argument.

Check Your Understanding

Use the three-term risk bound and the schedule conditions to answer these questions.

Which term in the bound is controlled by $n\lambda_n\to\infty$, and why is that condition not sufficient by itself?
Explain why universality for every fixed positive bandwidth does not bound the norm of an approximating score along a shrinking-bandwidth sequence.
In the power-law example, calculate the exponent of $\lambda_n\sigma_n^{-4}$ and verify that it is negative.
In the diagonal construction, why is it useful to choose $n_j\geq j/\lambda_j$?
What additional evidence would be needed before applying the power-law example's schedule to a new distribution and classification problem?