Adaptive Kernel Bandwidth Selection by Pairwise Comparison

Why Compare Bandwidths?

In kernel regression, a small bandwidth uses observations near the target location and tends to have low bias but high variance. A large bandwidth averages more broadly, often reducing variance while increasing bias. The central difficulty in adaptation is that the bias depends on the unknown regression function. Pairwise comparison addresses this by checking whether a smoother estimate differs “too much” from estimates using finer bandwidths.

The rule needs a threshold that reflects the random variability of each difference. Comparing every pair against one fixed numerical cutoff ignores the fact that different bandwidth pairs can have very different variances. We will use the variance of each pairwise contrast directly, and then give conditions under which the resulting choice has an oracle-type error bound.

Kernel Estimates and Pairwise Comparisons

Consider fixed design points \(x_1,\ldots,x_n\) and the Gaussian regression model

At a target point \(x\), a linear kernel estimate at bandwidth \(h\) can be written

The weights are determined by the kernel, the bandwidth, and the design. We assume the denominator used to define the kernel weights is nonzero. The mean and variance of this estimate are

Take a finite bandwidth grid \(h_1<\cdots<h_M\), ordered from finest to coarsest. For two grid indices \(k<j\), compare the coarser estimate at \(h_j\) with the finer estimate at \(h_k\). Their difference has noise variance

This is generally not \(V_{h_j}(x)+V_{h_k}(x)\), because estimates based on the same observations are correlated. The contrast variance automatically accounts for that dependence.

A Gaussian Threshold for the Whole Grid

A threshold should control the chance that random noise makes one of the many comparisons look unusually large. Let \(N=M(M-1)/2\) be the number of distinct pairs and set \(K=N+M\). For \(0<\delta<1\), define

The factor \(K\) allows simultaneous control of all pairwise noise contrasts and all individual estimator noises. The following result justifies this calibration.

Proof. Each centered pairwise difference is Gaussian with mean zero and variance \(V_{jk}\). When this variance is positive, dividing by its standard deviation gives a standard normal random variable \(Z\); the Gaussian tail bound gives \(P(|Z|>t)\leq 2e^{-t^2/2}\). The same argument applies to each centered estimate with positive variance. If any variance is zero, the corresponding centered quantity is identically zero, so its inequality holds automatically.

There are \(N\) pairwise contrasts and \(M\) individual estimates. For each nondegenerate quantity, the probability of exceeding its bound at \(t=q_\delta\) is at most \(2e^{-q_\delta^2/2}=\delta/K\). By the union bound, the probability that any of the \(K=N+M\) inequalities fails is at most \(K(\delta/K)=\delta\). Therefore all inequalities hold together with probability at least \(1-\delta\). \(\square\)

On this event, the random part of any pairwise difference is at most half the selection threshold, since \(\lambda=2q_\delta\). This leaves room for a deterministic difference between the mean estimates, which is the part caused by smoothing bias.

An Oracle Bound and Its Conditions

The relevant oracle is not necessarily the bandwidth with the smallest unknown mean squared error. It is a bandwidth whose mean estimates are sufficiently close to all finer mean estimates at the chosen comparison scale. This condition captures when the bias at that bandwidth is small enough for the pairwise rule to accept it.

Proof. Work on the simultaneous event in the preceding theorem. For each \(k<j_0\), split the observed difference into its mean difference and centered noise difference. The deterministic condition bounds the first by \((\lambda/2)\sqrt{V_{j_0k}}\); the event bounds the second by \(q_\delta\sqrt{V_{j_0k}}=(\lambda/2)\sqrt{V_{j_0k}}\). Their sum is at most \(\lambda\sqrt{V_{j_0k}}\), so \(j_0\) passes. Since the selected index is the largest passing index, \(\hat j\geq j_0\).

If \(\hat j=j_0\), their observed estimates are identical. Otherwise, because \(\hat j\) passes, it passes its comparison with the finer index \(j_0\). In either case, \[ |\hat f_{h_{\hat j}}-\hat f_{h_{j_0}}| \leq \lambda\sqrt{V_{\hat j,j_0}}. \] The triangle inequality for the standard deviation of a difference gives \(\sqrt{V_{\hat j,j_0}}\leq\sqrt{V_{h_{\hat j}}}+\sqrt{V_{h_{j_0}}}\). By the assumed nonincreasing variances and \(\hat j\geq j_0\), this is at most \(2\sqrt{V_{h_{j_0}}}\). Also, the simultaneous event bounds \(|\hat f_{h_{j_0}}-m_{h_{j_0}}|\leq q_\delta\sqrt{V_{h_{j_0}}}\). Combining these inequalities with the triangle inequality yields \[ |\hat f_{h_{\hat j}}-f| \leq 2\lambda\sqrt{V_{h_{j_0}}} +q_\delta\sqrt{V_{h_{j_0}}} +|m_{h_{j_0}}-f| =5q_\delta\sqrt{V_{h_{j_0}}}+|m_{h_{j_0}}-f|, \] because \(\lambda=2q_\delta\). The simultaneous event has probability at least \(1-\delta\), proving the claim. \(\square\)

The bound separates the oracle’s bias, \(|m_{h_{j_0}}(x)-f(x)|\), from a variance term. It is useful only if an index with a suitably small bias also meets the deterministic comparison condition. The theorem does not assert that such an index always exists, nor that the rule always finds the exact minimizer of mean squared error.

When the Rule Adapts—and When It Does Not

For a kernel estimate on a regular one-dimensional design, a common setting has variance of order \(\sigma^2/(nh)\) over bandwidths with enough observations in their kernel windows. If \(f\) is locally \(\beta\)-smooth and the kernel has appropriate moment properties, the bias is often of order \(h^\beta\). These facts motivate the bias–variance balance in the example, but a rate claim requires verifying them for the particular design and estimator.

To interpret the oracle bound as data-driven risk adaptation, the grid should cover useful bandwidth scales, the contrast variances should be known or estimated accurately enough, and there should be a bandwidth whose mean estimate has small bias and satisfies the deterministic comparison condition. A nonincreasing variance sequence is one convenient condition for the stated bound. The grid size also matters: a larger grid requires a more conservative simultaneous threshold. The method adapts by comparing estimates rather than by being given the smoothness \(\beta\), but adaptation is not automatic in the absence of these conditions.

A common mistake is to compare \(\hat f_{h_j}\) and \(\hat f_{h_k}\) using the variance of just one estimate, or to add their variances as if the estimates were independent. They usually use the same responses, so their covariance matters: \[ V_{jk}=V_{h_j}+V_{h_k}-2\operatorname{Cov}(\hat f_{h_j},\hat f_{h_k}). \] The correction is to compute the variance of the difference itself, using the difference in weights, and then calibrate the threshold for the number of comparisons being made.