Minimax Lower Bounds for Level Set Estimation

Why Lower Bounds Need Two Different Kinds of Separation

An estimator can fail to recover a density level set for two distinct reasons: the target sets may be far apart, while the data distributions that generate them are hard to distinguish. A minimax lower bound makes both statements precise. It constructs two admissible densities whose level sets are separated under the loss of interest, but whose \(n\)-sample distributions have small total variation distance. No estimator can reliably tell which target generated the observations, so it must incur substantial error for at least one of them.

Write \(A(p)=\{x:p(x)\geq\lambda\}\) for the superlevel set of a density \(p\) at a fixed threshold \(\lambda\). For measurable sets \(A,B\), symmetric-difference loss is \(\mu(A\triangle B)\), where \(\mu\) is Lebesgue measure and \(A\triangle B=(A\setminus B)\cup(B\setminus A)\). For nonempty compact sets, Hausdorff distance is \(d_H(A,B)=\max\{\sup_{x\in A}\inf_{y\in B}\|x-y\|,\sup_{y\in B}\inf_{x\in A}\|x-y\|\}\). These losses measure different features: symmetric difference measures the volume of disagreement, whereas Hausdorff distance detects the largest displacement, even if it occurs in a small region.

A Smooth Pair with Nearby Distributions

We give an explicit local construction on \([0,1]^d\), with \(d\geq2\). Fix a threshold \(\lambda=1\), a slope \(a\in(0,1)\), and a smoothness order \(\beta\geq1\). The smoothness class is understood to impose uniform bounds on derivatives through order \(\lfloor\beta\rfloor\), with the usual Hölder bound at noninteger order. Constants in the argument may depend on \(d,\beta,a\), and the chosen smoothness-class radius, but not on \(n\).

The baseline density and its target are

Indeed, \(\int_{[0,1]^d}p_0(x)\,dx=1\), since the integral of \(x_d-1/2\) is zero. Also \(p_0\geq1-a/2>0\). The formula for \(A_0\) is exact: \(p_0(x)\geq1\) if and only if \(x_d\geq1/2\). In particular, there is no extra boundary face at which the baseline returns to the threshold.

Choose a nonnegative \(C^\infty\) function \(b\), supported on \([-1/4,1/4]\), with \(b(0)>0\). For example, take \(b(t)=\exp\{-1/(1-16t^2)\}\) for \(|t|<1/4\), and \(b(t)=0\) otherwise. Set \(\eta(u)=\prod_{j=1}^{d-1}b(u_j)\) and \(\phi(v)=b(v)-b(v-1)\). Then \(\eta(0)>0\), \(\phi(0)=b(0)>0\), and \(\int_{\mathbb R}\phi(v)\,dv=0\), because the two terms are translates with equal integrals. Both functions are smooth and compactly supported.

Let \(z=(1/2,\ldots,1/2)\in(0,1)^{d-1}\). For sufficiently small \(h>0\), the scaled bump is supported inside the cube. Define

where \(\kappa>0\) is a sufficiently small constant. The perturbation integrates to zero: changing variables in the last coordinate gives a factor \(h\int\phi(v)\,dv=0\). Thus \(\int p_1=1\). Its absolute size is at most a constant times \(\kappa h^\beta\), so, for small \(\kappa\), \(p_1\) is bounded below by a positive constant. The scaled derivatives of order \(r\leq\lfloor\beta\rfloor\) have size at most a constant times \(\kappa h^{\beta-r}\); hence the perturbation has uniformly bounded \(C^\beta\) norm for \(0<h\leq1\). With a suitable baseline and class radius, both densities belong to the same smoothness class.

How Far Apart Are the Target Sets?

The bump is positive at the baseline boundary near \(x'=z\), because both \(\eta(0)\) and \(\phi(0)\) are positive. This choice of center matters: positivity at a point cannot be inferred merely from a bump being positive somewhere in its support.

Here are uniform bounds establishing the displacement. Choose a fixed open set \(U\subset\mathbb R^{d-1}\) around \(0\) and constants \(\eta_0,\phi_0>0\) such that \(\eta(u)\geq\eta_0\) for \(u\in U\) and \(\phi(v)\geq\phi_0\) for \(|v|\leq\epsilon\), for some \(\epsilon>0\). Such choices exist by continuity and positivity at zero. For \(x'=z+hu\) with \(u\in U\), define \(g_u(t)=p_1(z+hu,t)-1\). In the relevant vertical neighborhood, \[ g_u(1/2)=\kappa h^\beta\eta(u)\phi(0)>0. \] Moreover, \(g'_u(t)=a+\kappa h^{\beta-1}\eta(u)\phi'((t-1/2)/h)\). For \(\beta\geq1\), choosing \(\kappa\) small makes this derivative lie between \(a/2\) and \(3a/2\). The function is therefore strictly increasing there.

At \(t=1/2-C\kappa h^\beta\), with \(C\) larger than \(2\|\eta\|_\infty\|\phi\|_\infty/a\), the linear baseline decrease dominates the perturbation, so \(g_u(t)<0\). For small enough \(h\), this point lies in the neighborhood where the derivative bound holds. The intermediate value theorem and strict monotonicity give a unique root \(r(u)<1/2\) between these two heights. The mean value theorem and the derivative upper bound also give

The lower bound follows because \(g_u(1/2)-g_u(r(u))=g'_u(\xi)(1/2-r(u))\) for some \(\xi\), and \(g'_u(\xi)\leq3a/2\). The upper bound follows from the point where \(g_u\) is already negative. Thus the root is displaced by order \(\kappa h^\beta\) over a tangential region of width order \(h\).

Hausdorff separation uses a point, not a volume. At the centered tangential coordinate \(x'=z\), the same root argument applies because \(\eta(0)>0\). The point \(y=(z,(r(0)+1/2)/2)\) lies above the root and below \(1/2\), so it belongs to \(A_1\) but not \(A_0\). Since \(A_0=\{x_d\geq1/2\}\), its distance to \(A_0\) is exactly \(1/2-y_d=(1/2-r(0))/2\). Consequently \(d_H(A_0,A_1)\geq c_{\mathrm H}\kappa h^\beta\) for a constant \(c_{\mathrm H}>0\). The centered bump condition \(\eta(0)>0\) is essential to this particular pointwise argument.

Testing Turns Separation into a Risk Bound

To prove the inequality, define a test that selects the target closer to \(\widehat A\), breaking ties in favor of \(A_0\). If it selects \(A_1\) when \(A_0\) is true, then \(d(\widehat A,A_1)\leq d(\widehat A,A_0)\). The triangle inequality yields \(d(A_0,A_1)\leq d(A_0,\widehat A)+d(\widehat A,A_1)\leq2d(A_0,\widehat A)\). Thus on this testing error, the loss under \(P_0^n\) is at least \(d(A_0,A_1)/2\). The same argument gives loss at least that amount under \(P_1^n\) when the test selects \(A_0\).

For any test with error events \(B_0\) under \(P_0^n\) and \(B_1\) under \(P_1^n\), the sum of error probabilities is at least \(1-\operatorname{TV}(P_0^n,P_1^n)\). Indeed, if \(T\) is the event that the test selects 1, then \(P_0^n(T)+P_1^n(T^c)=1-[P_1^n(T)-P_0^n(T)]\geq1-\operatorname{TV}(P_0^n,P_1^n)\). Adding the two expected losses therefore gives at least \(d(A_0,A_1)\{1-\operatorname{TV}\}/2\). The larger of the two risks is at least half their sum, proving the displayed inequality. \(\square\)

Keeping the Sample Distributions Close

For one observation, let \(p_0,p_1\) be the densities above. Since \(p_1\) is uniformly bounded below, the chi-square bound on Kullback–Leibler divergence gives \(\operatorname{KL}(p_0,p_1)\leq\int (p_0-p_1)^2/p_1\). The perturbation is supported on a region of volume at most a constant times \(h^d\), and has magnitude at most a constant times \(\kappa h^\beta\). Hence \[ \operatorname{KL}(p_0,p_1)\leq C\kappa^2 h^{2\beta+d}. \] For \(n\) independent observations, divergence adds: \(\operatorname{KL}(P_0^n,P_1^n)=n\operatorname{KL}(p_0,p_1)\). Pinsker’s inequality, \(\operatorname{TV}(P,Q)\leq\sqrt{\operatorname{KL}(P,Q)/2}\), then implies that the sample total variation is at most \(1/2\) when \(h=c_h n^{-1/(2\beta+d)}\), with \(c_h>0\) chosen sufficiently small. This choice also ensures the supports remain inside the cube for sufficiently large \(n\).

Minimax Lower Bounds and a Common Pitfall

Combining the two-point inequality with the constructed pair gives the following conclusion. For any smoothness class that contains these densities and for all sufficiently large \(n\), constants \(c_1,c_2>0\) exist such that

These are lower bounds, not claims that an estimator attains the rates. To extend the two-point argument to the full class, note that the supremum risk over \(\mathcal P\) is at least the maximum risk over the particular pair \(p_0,p_1\). The constants absorb the fixed bump size and the choice of \(c_h\).

A common mistake is to show only that the two densities are close, then conclude that estimating their level sets must be difficult. Closeness alone says nothing about the target: the level sets could also be nearly identical. The construction must prove both a small divergence for the sample distributions and a positive separation under the chosen set loss. Another mistake is to infer Hausdorff separation from a large symmetric difference; a large volume disagreement does not in general force a large maximum distance. Here the direct witness point below the baseline boundary establishes Hausdorff separation independently.