Kernel Level Set Rates and Bandwidth Choice

From Density Error to Set Error

A kernel density estimate is useful for level-set estimation because a small error in estimated density often means a small error in the associated superlevel set. The word “often” matters: the conversion depends on how much space lies near the threshold, and on how sharply the density crosses it. This tutorial combines the kernel estimator’s bias and stochastic error with those two geometric conditions to obtain bandwidth-dependent bounds.

All set guarantees below are restricted to a specified compact region $D\subset\mathbb R^d$. This is important: smoothness near the level set does not, by itself, control a supremum over the whole space. Write $|A|$ for the Lebesgue measure of a measurable set $A$, and fix a threshold $\lambda>0$.

Definition: For a density $f$, the level set in $D$ is $L_\lambda=\{x\in D:f(x)\geq\lambda\}$. Given observations $X_1,\ldots,X_n$ and a kernel $K$, define $K_h(u)=h^{-d}K(u/h)$, $\widehat f_h(x)=n^{-1}\sum_{i=1}^n K_h(x-X_i)$, and the plug-in estimate $\widehat L_{\lambda,h}=\{x\in D:\widehat f_h(x)\geq\lambda\}$. The symmetric-difference loss is $|\widehat L_{\lambda,h}\triangle L_\lambda|$, where $A\triangle B=(A\setminus B)\cup(B\setminus A)$. The Hausdorff distance between nonempty compact sets $A,B$ is $d_H(A,B)=\max\{\sup_{a\in A}\inf_{b\in B}\|a-b\|,\sup_{b\in B}\inf_{a\in A}\|b-a\|\}$.

The Kernel Error on the Region of Interest

Suppose $X_1,\ldots,X_n$ are independent with density $f$. For a transparent rate statement, take an integer smoothness order $\beta\geq1$. Assume that $K$ is bounded, compactly supported, integrates to one, and has vanishing moments of every order from 1 through $\beta-1$. Assume also that its absolute moment of order $\beta$ is finite. On a fixed neighborhood of $D$, suppose $f$ has bounded derivatives through order $\beta$. These are local assumptions: when $K$ is supported in a ball of radius $R$, only the $Rh$-neighborhood of $D$ is needed for the bias calculation at bandwidth $h$.

For the stochastic part, use the standard uniform empirical-process condition on the translated kernel class. Concretely, suppose the class of functions $u\mapsto K((x-u)/h)$, indexed by $x\in D$ and the bandwidths under consideration, has a bounded envelope and VC-type covering numbers, and the density is bounded on the relevant neighborhood. The resulting uniform concentration bound, for polynomially decreasing $h$ with $nh^d/\log n\to\infty$, is of order $\sqrt{\log n/(nh^d)}$ with probability tending to one. We use the bound on $D$, not on all of $\mathbb R^d$.

Uniform-error bound: Under the conditions just stated, there is a constant $C$, independent of $n$ and $h$, such that with probability tending to one, $$ \sup_{x\in D}|\widehat f_h(x)-f(x)| \leq C\left(h^\beta+\sqrt{\frac{\log n}{nh^d}}\right) =:\delta_n. $$ The bias term requires the smoothness and moment assumptions on the $Rh$-neighborhood of $D$; the stochastic term requires the stated uniform concentration condition.

The bias order follows directly from a Taylor expansion. For fixed $x\in D$, the expectation of the estimate is $\int K(u)f(x-hu)\,du$. Expand $f(x-hu)$ through degree $\beta-1$. The constant term integrates to $f(x)$; every nonconstant polynomial term integrates to zero by the kernel moment conditions. The Taylor remainder is bounded by a constant times $h^\beta\|u\|^\beta$, uniformly over $x\in D$. Integrating its absolute value against $|K(u)|$ gives a bias bounded by $C h^\beta$. The stochastic term is the uniform concentration bound assumed above.

Worked Example: Balancing Bias and Stochastic Error

Take $d=2$, $\beta=2$, and $n=10^6$. Ignoring fixed constants, balance $h^2$ against $\sqrt{\log n/(nh^2)}$. Squaring the equality gives $h^4=\log n/(nh^2)$, hence $h^6=\log n/n$ and $$ h=\left(\frac{\log n}{n}\right)^{1/6} =\left(\frac{13.8155}{10^6}\right)^{1/6}\approx 0.155. $$

At this bandwidth, $h^2\approx0.0240$. Also $nh^2\approx 10^6(0.0240)=24{,}000$, so $\sqrt{\log n/(nh^2)}\approx\sqrt{13.8155/24{,}000}\approx0.0240$. The two terms have the same order, and their sum is about $0.048$, up to the constants in the bound.

Symmetric-Difference Rates Under a Margin Condition

Uniform density error alone does not guarantee small set error. If a large region has density almost equal to $\lambda$, even a small perturbation can change membership throughout that region. A margin condition rules out too much volume near the threshold.

Definition (margin condition): For constants $C_0>0$, $\alpha>0$, and $t_0>0$, the density satisfies a margin condition on $D$ at threshold $\lambda$ if $$ \left|\{x\in D:|f(x)-\lambda|\leq t\}\right|\leq C_0t^\alpha \qquad (0<t\leq t_0). $$

Theorem (plug-in symmetric-difference bound): If $\sup_{x\in D}|\widehat f_h(x)-f(x)|\leq\delta\leq t_0$, then under the margin condition, $$ |\widehat L_{\lambda,h}\triangle L_\lambda|\leq C_0\delta^\alpha. $$

Proof. If $x$ belongs to exactly one of $L_\lambda$ and $\widehat L_{\lambda,h}$, the two density values must lie on opposite sides of $\lambda$, allowing equality at the threshold. Thus \[ |f(x)-\lambda|\leq |f(x)-\widehat f_h(x)|\leq\delta. \] Therefore $\widehat L_{\lambda,h}\triangle L_\lambda\subseteq\{x\in D:|f(x)-\lambda|\leq\delta\}$. Taking Lebesgue measures and applying the margin condition proves the claim. $\square$

Combining this result with the uniform-error bound gives, with probability tending to one, a symmetric-difference error of order $\left(h^\beta+\sqrt{\log n/(nh^d)}\right)^\alpha$, provided the error is at most $t_0$. This is a bound for volume loss. A probability-mass version requires a corresponding margin condition stated using probability mass rather than Lebesgue measure.

Worked Example: A Margin Condition Converts Density Error to Volume Error

Suppose a target region satisfies the margin condition with $C_0=3$, $\alpha=1/2$, and $t_0=0.1$. If the uniform density error is at most $\delta=0.04$, then $0.04\leq t_0$, and $$ |\widehat L_{\lambda,h}\triangle L_\lambda| \leq 3(0.04)^{1/2} =3(0.2)=0.6. $$

The bound is an upper bound on volume, not a claim that the error equals $0.6$. Its rate is the relevant feature: halving the density error multiplies the bound by $2^{-1/2}$. In particular, the exponent $\alpha$ determines how strongly a density error translates into symmetric-difference loss.

Hausdorff Error Under Boundary Separation

For boundary location, a gradient condition is useful because it controls how quickly the density moves away from the threshold. A nonzero gradient on the level boundary is a familiar sufficient local regularity condition, but a Hausdorff conclusion also needs the boundary to be well behaved and the level set not to have unrelated, nearly-threshold regions elsewhere in $D$. The following explicit separation condition makes those requirements visible.

Boundary-separation condition: Let $\Gamma=\{x\in D:f(x)=\lambda\}$ be a compact regular boundary lying in the interior of $D$. Suppose there is a tube of radius $r>0$ around $\Gamma$ in which points have a signed distance $s(x)$, positive on the $L_\lambda$ side and negative outside. Assume $|f(x)-\lambda|\geq g|s(x)|$ in this tube, for some $g>0$. Assume also that the boundary has inward and outward normal segments of length $r$, and that points outside the tube are separated from the threshold by at least $gr$. These conditions hold, for example, in a sufficiently small tube around a compact smooth boundary when the normal derivative is bounded away from zero, with appropriate separation elsewhere in $D$.

Theorem (Hausdorff bound from boundary separation): Under the boundary-separation condition, suppose $\widehat f_h$ is continuous and $\sup_D|\widehat f_h-f|\leq\delta$, with $2\delta/g<r$. Then the estimated and true level sets are nonempty and $$ d_H(\widehat L_{\lambda,h},L_\lambda)\leq \frac{2\delta}{g}. $$

Proof. First take $x\in\widehat L_{\lambda,h}\setminus L_\lambda$. Then $f(x)<\lambda\leq\widehat f_h(x)$, so $\lambda-f(x)\leq|\widehat f_h(x)-f(x)|\leq\delta$. Separation outside the tube rules out such a point there when $\delta<gr$; within the tube it gives $|s(x)|\leq\delta/g$. Thus every estimated point outside the true set is within $\delta/g$ of its boundary.

Now take $x\in L_\lambda$. If its signed distance from the boundary is at least $\delta/g$, then $f(x)-\lambda\geq\delta$, so $\widehat f_h(x)\geq\lambda$ and $x\in\widehat L_{\lambda,h}$. Otherwise, move from $x$, if needed, along an inward normal to a point $y$ at distance $2\delta/g$ inside the boundary. The normal segment exists by assumption. Boundary separation gives $f(y)-\lambda\geq2\delta$, hence $\widehat f_h(y)\geq\lambda+\delta>\lambda$. The distance from $x$ to this estimated-set point is at most $2\delta/g$. These two directions establish the Hausdorff bound. $\square$

Applying the uniform-error bound yields a Hausdorff rate of order $\left(h^\beta+\sqrt{\log n/(nh^d)}\right)/g$, subject to the stated geometry and continuity conditions. For a continuous kernel, the kernel estimate is continuous. The bound is local in its smoothness requirement, but the separation condition must also rule out remote points in $D$ whose density is arbitrarily close to $\lambda$.

Worked Example: Boundary Location for a Normal Density

Let $f$ be the standard normal density on $D=[-2,2]$, and set $\lambda=\phi(1)$, where $\phi(x)=(2\pi)^{-1/2}e^{-x^2/2}$. The level set is $L_\lambda=[-1,1]$, with boundary $\Gamma=\{-1,1\}$. In the tube of radius $0.1$ around either boundary point, $|x|\in[0.9,1.1]$ and $|f'(x)|=|x|\phi(x)$. Its minimum on this range is greater than $0.239$, so the mean value theorem gives boundary separation with $g=0.23$ throughout the tube.

If the density estimate is uniformly within $\delta=0.01$, then $2\delta/g=0.02/0.23\approx0.087<0.1$. Provided the separation condition holds away from the tube as well, the theorem gives $d_H(\widehat L_{\lambda,h},L_\lambda)\leq0.087$. The gradient matters through $1/g$: a shallower crossing gives a larger location error for the same density error.

Choosing the Bandwidth

The uniform-error bound has a decreasing bias term and an increasing stochastic term as $h$ becomes smaller. Balancing their orders gives $$ h^\beta\asymp\sqrt{\frac{\log n}{nh^d}} \quad\Longleftrightarrow\quad h^{2\beta+d}\asymp\frac{\log n}{n}, \qquad h\asymp\left(\frac{\log n}{n}\right)^{1/(2\beta+d)}. $$ At this bandwidth, both terms have order $(\log n/n)^{\beta/(2\beta+d)}$. The resulting plug-in bounds are $$ |\widehat L_{\lambda,h}\triangle L_\lambda| =O_p\!\left(\left(\frac{\log n}{n}\right)^{\alpha\beta/(2\beta+d)}\right), \qquad d_H(\widehat L_{\lambda,h},L_\lambda) =O_p\!\left(\frac{1}{g}\left(\frac{\log n}{n}\right)^{\beta/(2\beta+d)}\right), $$ under their respective margin and boundary-separation assumptions. Here $O_p$ denotes stochastic order. This balancing chooses the bandwidth that optimizes the displayed uniform-error bound; it does not, by itself, prove a minimax-optimal rate.

Worked Example: Reading Off the Symmetric-Difference Rate

Take $d=2$, smoothness $\beta=2$, and margin exponent $\alpha=1/2$. The balanced bandwidth is $h\asymp(\log n/n)^{1/6}$, and the density error is of order $(\log n/n)^{1/3}$. Raising this error to the margin exponent gives $$ |\widehat L_{\lambda,h}\triangle L_\lambda| =O_p\!\left(\left(\frac{\log n}{n}\right)^{(1/3)(1/2)}\right) =O_p\!\left(\left(\frac{\log n}{n}\right)^{1/6}\right). $$

The exponent is the product $\alpha\beta/(2\beta+d)$. A weaker margin condition (smaller $\alpha$) makes set-volume error decay more slowly, even though the density estimator and its bandwidth have not changed.

Common Pitfalls and Practical Meaning

The bounds separate three roles. Smoothness and kernel moments control bias; sample size, dimension, bandwidth, and the kernel-class concentration condition control stochastic error; and the margin or boundary-separation condition converts density error into a particular set loss. A method can estimate density uniformly well and still have poor boundary localization if the density crosses the threshold weakly.

Taking a local assumption to a global supremum. Smoothness near the target set justifies a bound on a specified region and its kernel neighborhoods, not automatically $\sup_{x\in\mathbb R^d}|\widehat f_h(x)-f(x)|$. A cusp elsewhere can have slower bias decay. Restrict the supremum to the region where the assumptions hold, or impose global smoothness if a global bound is needed.
Using a margin condition for Hausdorff loss. The margin condition controls the volume of a threshold strip, so it yields symmetric-difference error. It does not alone prevent a small, distant component from appearing or disappearing. Hausdorff control needs geometric and separation assumptions.
Ignoring the range of the margin bound. The condition is stated only for $t\leq t_0$; the derived set bound requires the density error $\delta$ to lie in that range.
Calling a balanced bandwidth universally optimal. Balancing optimizes the stated upper bound under its assumptions. Different losses, unknown smoothness, boundary effects, or spatially varying regularity can call for other choices.

Key takeaway: First obtain a valid uniform density-error bound on the region being estimated. Then use a margin condition for symmetric-difference loss or boundary separation for Hausdorff loss. Bandwidth determines the density-error scale; geometry determines how that error becomes set error.

Check Your Understanding

Try these questions before moving on.

Why does a smoothness assumption only near the level boundary fail to justify a global supremum bound for the kernel density estimate?
Show why a point in the symmetric difference must satisfy $|f(x)-\lambda|\leq\delta$ when the uniform density error is at most $\delta$.
For dimension $d$ and smoothness $\beta$, solve the bias–stochastic-error balance for the bandwidth and the resulting density-error order.
Which loss is directly controlled by a margin condition, and why does that condition alone not ensure Hausdorff control?
In the boundary-separation result, what happens to the Hausdorff bound as the crossing strength $g$ decreases?