Confidence Bands for Level Set Boundaries

From Density Uncertainty to Boundary Uncertainty

A confidence band for a density describes uncertainty in its values, but the target in level-set estimation is often geometric: the boundary separating locations above a threshold from those below it. Translating one kind of uncertainty into the other requires care. A small density error does not, by itself, imply a small boundary error; the density must also change sufficiently quickly near the boundary.

Let $D\subset\mathbb{R}^d$ be compact, let $f:D\to\mathbb{R}$ be continuous, and fix a level $\lambda$. Write $L_\lambda=\{x\in D:f(x)\geq\lambda\}$, and let $\Gamma_\lambda=\partial_D L_\lambda$ be its boundary relative to $D$. Assume that $\Gamma_\lambda=\{x\in D:f(x)=\lambda\}$, so there are no level-$\lambda$ plateau points in the interior of the superlevel set. The distance from $x$ to the boundary is $d(x,\Gamma_\lambda)=\inf_{z\in\Gamma_\lambda}\|x-z\|$.

Definition: A uniform confidence band with half-width $\varepsilon>0$ for $f$ is the pair of functions $\hat f-\varepsilon$ and $\hat f+\varepsilon$, where $\hat f$ is an estimator, together with a coverage guarantee $P(\|\hat f-f\|_\infty\leq\varepsilon)\geq 1-\alpha$. The associated boundary confidence set is $$ C_\varepsilon=\{x\in D:|\hat f(x)-\lambda|\leq\varepsilon\}. $$ On the coverage event, this set is intended to contain the unknown boundary.

The value band also gives a bracket for the whole superlevel set. Define $L^-=\{x\in D:\hat f(x)\geq\lambda+\varepsilon\}$ and $L^+=\{x\in D:\hat f(x)\geq\lambda-\varepsilon\}$. The first is a conservative inner set and the second a conservative outer set. The boundary confidence set $C_\varepsilon$ is different: it localizes where the boundary may lie rather than estimating the entire superlevel region.

Worked Conversions

Worked Example: Bracketing a Superlevel Set

On $D=[-1,1]$, take the density $f(x)=(1+x)/2$, threshold $\lambda=1/2$, and estimator $\hat f(x)=1/2+0.6x$. The density $f$ is nonnegative and integrates to one. Although $\hat f$ integrates to one, it is not nonnegative on $D$ (for example, $\hat f(-1)=-0.1$), so it is not a density-valued estimator. The uniform error is $\|\hat f-f\|_\infty=\sup_{x\in[-1,1]}|0.1x|=0.1$, so use $\varepsilon=0.1$.

The true superlevel set is $L_\lambda=\{x:(1+x)/2\geq1/2\}=[0,1]$. The inner bracket is $L^-=\{x:1/2+0.6x\geq0.6\}=[1/6,1]$, and the outer bracket is $L^+=\{x:1/2+0.6x\geq0.4\}=[-1/6,1]$. Thus $L^-\subseteq L_\lambda\subseteq L^+$. The boundary confidence set is $C_\varepsilon=\{x:|0.6x|\leq0.1\}=[-1/6,1/6]$, which contains the true boundary point $0$.

Worked Example: Geometric Localization With the Factor of Two

Keep $D=[-1,1]$, $f(x)=(1+x)/2$, and $\lambda=1/2$, so $\Gamma_\lambda=\{0\}$. Here $|f(x)-\lambda|=|x|/2$, hence the margin condition holds with $\gamma=1/2$ and $r_0=1$. Let $\hat f=f+0.08$. Its uniform error is $0.08$, so take $\varepsilon=0.08$. The required condition is $2\varepsilon=0.16<\gamma r_0=0.5$.

The boundary confidence set solves $|x/2+0.08|\leq0.08$. Subtracting $0.08$ gives $-0.16\leq x/2\leq0$, hence $C_\varepsilon=[-0.32,0]$. Its farthest point from $\Gamma_\lambda$ is at distance $0.32$, exactly $2\varepsilon/\gamma=0.16/0.5=0.32$. The example shows why the geometric guarantee uses $2\varepsilon$, not $\varepsilon$, when the band itself is defined by $|\hat f-\lambda|\leq\varepsilon$.

Coverage and Geometric Width

A margin condition converts a density-value discrepancy into a distance. We state it in a form that controls both points near the boundary and points farther away. The second clause is essential: without it, an additional region far from the boundary could have density values arbitrarily close to $\lambda$.

Margin condition: For constants $\gamma>0$ and $r_0>0$, assume that $$ |f(x)-\lambda|\geq\gamma d(x,\Gamma_\lambda) \quad\text{if }d(x,\Gamma_\lambda)\leq r_0, $$ and $$ |f(x)-\lambda|\geq\gamma r_0 \quad\text{if }d(x,\Gamma_\lambda)>r_0. $$

The first result gives a set-valued confidence guarantee. The estimator and its confidence radius are assumed measurable enough that the events and sets in the statement are well-defined. The radius $\varepsilon$ is fixed; the same argument applies to a random radius if the stated uniform error event holds with that radius and the resulting events are measurable.

Theorem (coverage and localization): Suppose the margin condition holds and $P(\|\hat f-f\|_\infty\leq\varepsilon)\geq1-\alpha$, where $2\varepsilon<\gamma r_0$. Then, with probability at least $1-\alpha$, $$ \Gamma_\lambda\subseteq C_\varepsilon \subseteq\{x\in D:d(x,\Gamma_\lambda)\leq 2\varepsilon/\gamma\}. $$ In particular, if the sets are nonempty, the Hausdorff distance between $C_\varepsilon$ and $\Gamma_\lambda$ is at most $2\varepsilon/\gamma$.

Proof. Let $E=\{\|\hat f-f\|_\infty\leq\varepsilon\}$, which has probability at least $1-\alpha$. On $E$, every $x\in\Gamma_\lambda$ satisfies $f(x)=\lambda$, and therefore $|\hat f(x)-\lambda|=|\hat f(x)-f(x)|\leq\varepsilon$. This proves $\Gamma_\lambda\subseteq C_\varepsilon$.

Now take $x\in C_\varepsilon$. On the same event, the triangle inequality gives $$ |f(x)-\lambda|\leq |f(x)-\hat f(x)|+|\hat f(x)-\lambda| \leq\varepsilon+\varepsilon=2\varepsilon. $$ If $d(x,\Gamma_\lambda)>r_0$, the outside-tube condition would imply $|f(x)-\lambda|\geq\gamma r_0>2\varepsilon$, a contradiction. Thus $d(x,\Gamma_\lambda)\leq r_0$, and the local margin condition yields $\gamma d(x,\Gamma_\lambda)\leq|f(x)-\lambda|\leq2\varepsilon$. Hence $d(x,\Gamma_\lambda)\leq2\varepsilon/\gamma$. Both inclusions hold on $E$, so they hold with probability at least $1-\alpha$. Since $\Gamma_\lambda\subseteq C_\varepsilon$, the distance from each point of $\Gamma_\lambda$ to $C_\varepsilon$ is zero; the other directed distance is bounded by $2\varepsilon/\gamma$. This proves the Hausdorff claim. $\square$

The radius $2\varepsilon/\gamma$ is an outer radius around the boundary; it is not the full thickness of a two-sided tube. A tube of radius $r$ can extend up to distance $r$ on each side, giving a total transverse width of $2r$. Here the confidence-set guarantee says that every candidate boundary point is within radius $2\varepsilon/\gamma$ of the true boundary.

Worked Example: Checking a Confidence Level and Tube Condition

Suppose a procedure gives $P(\|\hat f-f\|_\infty\leq0.04)\geq0.95$. Assume the boundary satisfies the margin condition with $\gamma=0.2$ and $r_0=0.5$. The required numerical check is $2\varepsilon=0.08<\gamma r_0=0.2(0.5)=0.1$, which is satisfied.

The theorem therefore gives, with probability at least $0.95$, $\Gamma_\lambda\subseteq C_{0.04}$ and $C_{0.04}\subseteq\{x:d(x,\Gamma_\lambda)\leq2(0.04)/0.2\}$. The radius is $0.08/0.2=0.4$. It is less than $r_0=0.5$, as required for the local margin calculation. If instead the uniform error radius were $0.06$, then $2\varepsilon=0.12>0.1$; this theorem would not provide localization, even if the value band still covered the boundary.

Why the Margin Condition Matters

The density error $\varepsilon$ is measured vertically, in density units. Boundary error is measured horizontally, in distance units. The margin constant $\gamma$ describes how rapidly density values separate from $\lambda$ as one moves away from the boundary. A larger $\gamma$ produces a narrower geometric confidence set for the same value error. If $\gamma$ is small, the density is nearly flat near the threshold, and modest vertical uncertainty can leave substantial positional uncertainty.

For a sequence of estimators, suppose deterministic radii $\varepsilon_n$ satisfy $P(\|\hat f-f\|_\infty\leq\varepsilon_n)\geq1-\alpha$, with fixed $\gamma,r_0>0$ and $2\varepsilon_n<\gamma r_0$. The theorem gives a boundary confidence-set radius $2\varepsilon_n/\gamma$ at the same confidence level. Thus any shrinking uniform error radius yields a shrinking geometric radius when the margin constants remain bounded away from zero. This conclusion concerns boundary localization; it does not by itself establish topological correctness, such as the number of connected components.

Result (superlevel-set bracket): On the event $\|\hat f-f\|_\infty\leq\varepsilon$, $$ \{x:\hat f(x)\geq\lambda+\varepsilon\} \subseteq L_\lambda \subseteq \{x:\hat f(x)\geq\lambda-\varepsilon\}. $$

Proof. If $\hat f(x)\geq\lambda+\varepsilon$, then $f(x)\geq\hat f(x)-\varepsilon\geq\lambda$, so $x\in L_\lambda$. Conversely, if $f(x)\geq\lambda$, then $\hat f(x)\geq f(x)-\varepsilon\geq\lambda-\varepsilon$, so $x$ belongs to the outer set. $\square$

This bracket requires no margin condition: it follows from uniform value coverage alone. The margin and outside-tube assumptions enter only when converting the value uncertainty into a geometric bound on the boundary confidence set.

Common Pitfall

A tempting argument is to take $x\in C_\varepsilon$, write $|f(x)-\lambda|\leq\varepsilon$, and conclude $d(x,\Gamma_\lambda)\leq\varepsilon/\gamma$. The first inequality is not justified: $C_\varepsilon$ controls $|\hat f(x)-\lambda|$, while the estimator may differ from $f$ by another $\varepsilon$. The triangle inequality gives only $|f(x)-\lambda|\leq2\varepsilon$, so the valid radius for this band is $2\varepsilon/\gamma$, under $2\varepsilon<\gamma r_0$. A sharper radius would require a differently defined band and a separately proved error bound.

There is a second common mistake: using the local margin inequality everywhere. That inequality is assumed only within distance $r_0$ of the boundary. The outside-tube condition rules out points farther away whose density is still close enough to $\lambda$ to enter the candidate band. The condition $2\varepsilon<\gamma r_0$ then excludes those points from $C_\varepsilon$, allowing the local inequality to be used.

Key takeaway: Uniform density coverage gives boundary coverage through a value band and brackets the superlevel set. To guarantee geometric localization, combine the triangle inequality, a local margin condition, and an outside-tube separation condition. For $C_\varepsilon=\{|\hat f-\lambda|\leq\varepsilon\}$, the resulting radius is $2\varepsilon/\gamma$, not $\varepsilon/\gamma$.

Check Your Understanding

Use the definitions and results above to answer the following questions.

Why does $\Gamma_\lambda\subseteq C_\varepsilon$ follow from a uniform error bound when $f(x)=\lambda$ on the boundary?
For $x\in C_\varepsilon$, show which two terms in the triangle inequality produce the bound $2\varepsilon$.
What role does the outside-tube condition play in the localization proof?
If $\varepsilon=0.03$, $\gamma=0.15$, and $r_0=0.5$, does the theorem's tube condition hold, and what radius does it give?
Which confidence guarantee requires a margin condition: the inner/outer superlevel-set bracket or the geometric boundary localization?