Hausdorff Error from Gradient Separation

Why Boundary Geometry Matters

A uniform error bound for a density estimate controls how much the estimated density can differ from the truth at any point. It does not, by itself, say how far a level-set boundary can move. That distance also depends on how quickly the true density changes as one moves across the boundary. Where the density changes steeply, a small vertical error produces a small spatial displacement. Where it is nearly flat, even a small vertical error can move the level set much farther.

This tutorial turns that intuition into a deterministic result. For a density $f$, threshold $\lambda$, and estimate $\hat f$, write $L_\lambda(f)=\{x:f(x)\geq\lambda\}$. We will show that if $\hat f$ is uniformly within $\varepsilon$ of $f$, and the gradient stays bounded away from zero near the target level, then the Hausdorff error is at most a constant times $\varepsilon$. The assumptions must cover the whole relevant level band, not just selected points on the boundary.

Uniform Error Gives a Sandwich

Definition: For nonempty compact sets $A,B\subset\mathbb R^d$, their Hausdorff distance is $$ d_H(A,B)=\max\left\{\sup_{a\in A}\inf_{b\in B}\|a-b\|,\ \sup_{b\in B}\inf_{a\in A}\|b-a\|\right\}. $$ For a function $g$, its superlevel set at threshold $t$ is $L_t(g)=\{x:g(x)\geq t\}$.

The first step uses only uniform approximation. It does not require differentiability.

Theorem (level-set sandwich): If $\sup_x|\hat f(x)-f(x)|\leq\varepsilon$, then $$ L_{\lambda+\varepsilon}(f)\subseteq L_\lambda(\hat f)\subseteq L_{\lambda-\varepsilon}(f). $$

Proof. If $f(x)\geq\lambda+\varepsilon$, then $\hat f(x)\geq f(x)-\varepsilon\geq\lambda$, so $x\in L_\lambda(\hat f)$. Conversely, if $\hat f(x)\geq\lambda$, then $f(x)\geq\hat f(x)-\varepsilon\geq\lambda-\varepsilon$, so $x\in L_{\lambda-\varepsilon}(f)$. These implications give both inclusions. $\square$

The sandwich is not yet a distance bound. It says the estimated set lies between two nearby-threshold sets, but those sets might be far apart. Gradient separation supplies the missing geometric control.

Gradient Separation and a Displacement Lemma

Definition: Let $\delta>0$. The density $f$ has gradient separation $g>0$ on the band around $\lambda$ if $f$ is twice continuously differentiable on a neighborhood of $$ B_\delta=\{x:|f(x)-\lambda|\leq\delta\} $$ and $\|\nabla f(x)\|\geq g$ for every $x\in B_\delta$.

The condition says that the density has no critical points in the band of values relevant to the threshold perturbation. We also require $B_\delta$ to be compact; this ensures that the gradient-flow path used below cannot escape to infinity while its density value remains in the band.

Lemma (displacement across a level band): Suppose $B_\delta$ is compact and $f$ has gradient separation $g>0$ there. If $x\in B_\delta$ and $t$ lies between $f(x)$ and $\lambda$, then there is a point $y$ with $f(y)=t$ such that $$ \|x-y\|\leq \frac{|f(x)-t|}{g}. $$

Proof. On a neighborhood of $B_\delta$, define $V(x)=\nabla f(x)/\|\nabla f(x)\|$. The assumptions make $V$ continuously differentiable there, with speed $\|V(x)\|=1$. If $t>f(x)$, follow the differential equation $z'(s)=V(z(s))$, starting at $z(0)=x$. Along this path, $$ \frac{d}{ds}f(z(s))=\nabla f(z(s))\mathbin{\cdot}V(z(s))=\|\nabla f(z(s))\|\geq g. $$ If $t<f(x)$, instead follow $z'(s)=-V(z(s))$; then $f(z(s))$ decreases at rate at least $g$. Until the path reaches $t$, its density value stays between $f(x)$ and $t$, so it stays in the compact band $B_\delta$. The differential equation therefore continues until that value is reached. The required travel time is at most $|f(x)-t|/g$, since the density changes at rate at least $g$. The path has unit speed, so its length, and hence the distance from its starting point, is at most that travel time. Taking its endpoint as $y$ proves the claim. $\square$

The Hausdorff Bound

Theorem (Hausdorff error under gradient separation): Suppose $0<\varepsilon\leq\delta$, $B_\delta$ is compact, and $f$ has gradient separation $g>0$ on $B_\delta$. Assume $L_{\lambda-\delta}(f)$ and $L_\lambda(\hat f)$ are nonempty compact sets, and $\sup_x|\hat f(x)-f(x)|\leq\varepsilon$. Then $$ d_H\bigl(L_\lambda(\hat f),L_\lambda(f)\bigr)\leq\frac{\varepsilon}{g}. $$

Proof. The sandwich theorem gives $L_\lambda(\hat f)\subseteq L_{\lambda-\varepsilon}(f)$. Take $x\in L_\lambda(\hat f)$. If $f(x)\geq\lambda$, then $x\in L_\lambda(f)$, so its distance to the true set is zero. Otherwise $\lambda-\varepsilon\leq f(x)<\lambda$. The displacement lemma, with target $t=\lambda$, gives a point $y\in L_\lambda(f)$ satisfying $\|x-y\|\leq\varepsilon/g$. This bounds the distance from every estimated-set point to the true set.

For the other direction, take $x\in L_\lambda(f)$. If $f(x)\geq\lambda+\varepsilon$, the sandwich inclusion $L_{\lambda+\varepsilon}(f)\subseteq L_\lambda(\hat f)$ gives $x\in L_\lambda(\hat f)$. Otherwise $\lambda\leq f(x)<\lambda+\varepsilon$. Apply the displacement lemma with target $t=\lambda+\varepsilon$ to obtain $y\in L_{\lambda+\varepsilon}(f)$ with $\|x-y\|\leq\varepsilon/g$. The sandwich puts $y$ in $L_\lambda(\hat f)$. Thus each true-set point is within $\varepsilon/g$ of the estimated set as well. Taking the larger of the two directed distances proves the result. $\square$

The rate is linear in the uniform density error, with inverse gradient separation as the geometric factor. The theorem is deterministic: a probabilistic result follows by applying it on the event that the uniform error is at most $\varepsilon$, provided the stated set and regularity conditions hold.

Worked Examples

Worked Example: A Gaussian Density at a Regular Boundary

Let $f$ be the $N(0,1)$ density, $f(x)=(2\pi)^{-1/2}e^{-x^2/2}$, and set $\lambda=f(1)$. Then $L_\lambda(f)=[-1,1]$. Suppose a compact estimated superlevel set is formed from an estimate satisfying $\sup_x|\hat f(x)-f(x)|\leq0.01$.

The derivative is $f'(x)=-xf(x)$, so $|f'(x)|=|x|f(x)$. At the edges of the interval $0.8\leq |x|\leq1.2$, the values of the density are $f(0.8)\approx0.28969$, $f(1)\approx0.24197$, and $f(1.2)\approx0.19419$. Both endpoint differences from $f(1)$ exceed $0.047$. Since $f$ decreases with $|x|$, every point with $|f(x)-\lambda|\leq0.01$ lies in $0.8\leq|x|\leq1.2$.

On this band, $|x|f(x)$ has minimum at one of the interval endpoints: $0.8f(0.8)\approx0.23175$ and $1.2f(1.2)\approx0.23303$. Thus we may take $g=0.231$. The theorem gives $$ d_H\bigl(L_\lambda(\hat f),[-1,1]\bigr)\leq\frac{0.01}{0.231}<0.0433. $$

This bound does not claim that the actual boundary moves by exactly this amount; it is a guaranteed upper bound under the stated uniform-error assumption.

Worked Example: A Normalized Parabolic Density

On $[-1,1]$, let $f(x)=\tfrac34(1-x^2)$, and set $f(x)=0$ outside this interval. This is a density because $$ \int_{-1}^{1}\frac34(1-x^2)\,dx=\frac34\left(2-\frac23\right)=1. $$ Choose $\lambda=3/8$. Solving $\tfrac34(1-x^2)=3/8$ gives $x^2=1/2$, so $L_\lambda(f)=[-1/\sqrt2,1/\sqrt2]$.

Near either boundary, $|f'(x)|=\tfrac32|x|$. In the intervals of radius $0.1$ around the two boundary points, $|x|\geq1/\sqrt2-0.1$, and therefore $|f'(x)|\geq\tfrac32(1/\sqrt2-0.1)>0.91$. The density differences at the two ends of these intervals exceed $0.09$: at $x=1/\sqrt2-0.1$, $f(x)-\lambda\approx0.0986$; at $x=1/\sqrt2+0.1$, $\lambda-f(x)\approx0.1136$. By symmetry the same holds at the negative boundary. Consequently the band $|f(x)-\lambda|\leq0.03$ is contained in these intervals.

For any compact estimated superlevel set with uniform error at most $0.03$, the theorem applies with $g=0.91$, giving $$ d_H\bigl(L_\lambda(\hat f),L_\lambda(f)\bigr)\leq\frac{0.03}{0.91}<0.0330. $$ The density is set to zero outside $[-1,1]$, but the relevant band is strictly inside the support, where it is differentiable.

Worked Example: A Flat Quartic Boundary

Consider the normalized density $f(x)=\tfrac58(1-x^4)$ on $[-1,1]$, set to zero outside. Its integral is $\tfrac58(8/5)=1$. At the threshold $\lambda=5/8$, the superlevel set is $L_\lambda(f)=\{0\}$, because the density attains its maximum only at zero. The derivative $f'(x)=-\tfrac52x^3$ vanishes at this boundary.

Lower the threshold by $\eta>0$, with $\eta<5/8$. Solving $f(x)\geq\lambda-\eta$ gives $$ \frac58(1-x^4)\geq\frac58-\eta \quad\Longleftrightarrow\quad |x|\leq\left(\frac{8\eta}{5}\right)^{1/4}. $$ Thus $L_{\lambda-\eta}(f)$ is an interval of radius $(8\eta/5)^{1/4}$, and its Hausdorff distance from $L_\lambda(f)=\{0\}$ is exactly that radius. The displacement is of order $\eta^{1/4}$, not order $\eta$. The gradient-separation theorem cannot apply here: no positive $g$ bounds the gradient away from zero on the relevant band as the band shrinks to the flat maximum. This example shows why an error bound linear in $\varepsilon$ needs geometric assumptions.

Common Pitfall and Practical Meaning

A common mistake is to argue that a small uniform error automatically means a small Hausdorff error. The sandwich only places the estimated set between two true superlevel sets; it does not control how far apart those sets are. The quartic example shows that their separation can be much larger than the threshold perturbation when the density is flat. A second mistake is to check the gradient only at a few boundary points and infer a global Hausdorff guarantee. The theorem requires control on the whole relevant band, along with compactness and nonempty compact level sets; these conditions rule out problematic paths or distant near-threshold regions.

Hausdorff error is useful when the location of the boundary matters, rather than only the amount of probability mass misclassified. Gradient separation supplies a direct conversion from vertical density error to spatial boundary error. When that condition fails, a different displacement relationship may still be available, but its rate must reflect the local shape of the density rather than assuming linear behavior.

Check Your Understanding

Use the definitions, sandwich, and displacement argument to answer these questions.

Which inclusion in the level-set sandwich follows from $f(x)\geq\lambda+\varepsilon$, and which follows from $\hat f(x)\geq\lambda$?
Why does gradient separation bound the length of a path needed to reach a nearby density level?
In the Hausdorff theorem, how is a point in $L_\lambda(\hat f)$ handled when its true density is already at least $\lambda$?
For the quartic density, what is the radius of $L_{\lambda-\eta}(f)$, and why does it contradict a general linear displacement claim?
Why is checking the gradient only at the target boundary insufficient for the stated global theorem?