Worked Minimax Rate Derivations for Density Level Sets

From Density Error to Set-Recovery Error

A density level set is the region where a density exceeds a chosen threshold. Its estimator is often obtained by thresholding a density estimate, but the resulting set error is not simply the density-estimation error: the geometry and probability mass near the boundary matter. This tutorial works through that translation and compares it with lower bounds that describe how well any estimator can do.

Let \(X_1,\ldots,X_n\) be independent observations with density \(f\) on \(\mathbb{R}^d\), and fix a threshold \(\lambda>0\). Define the target set \(L=\{x:f(x)\geq\lambda\}\) and the estimated set \(\widehat L=\{x:\widehat f(x)\geq\lambda\}\). We measure set error in two ways. The symmetric-difference loss is \(P(L\triangle\widehat L)\), where \(A\triangle B=(A\setminus B)\cup(B\setminus A)\), and \(P\) denotes probability under density \(f\). The Hausdorff distance between nonempty compact sets \(A,B\) 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\|\}\).

The margin condition limits how much probability lies in a thin band of density values around \(\lambda\). The gradient condition instead controls how quickly density changes in the direction normal to the boundary. They control different losses and should not be substituted for one another. For a regular boundary with density positive there, a nonzero gradient commonly yields \(\alpha=1\), but a stated margin condition can cover more general situations.

Density Estimation and the Bandwidth Calculation

For a kernel density estimator, take a bounded, integrable kernel \(K\) with integral one and suitable vanishing moments for the desired smoothness, and set \(K_h(u)=h^{-d}K(u/h)\). Then \(\widehat f_h(x)=n^{-1}\sum_{i=1}^n K_h(x-X_i)\). Under the usual bounded-density and kernel regularity conditions, the bias is of order \(h^\beta\), while the pointwise standard deviation is of order \((nh^d)^{-1/2}\). For uniform error over a compact domain, a typical high-probability bound includes a logarithm:

Balancing the two terms gives the bandwidth and error scale used below. The logarithm is associated with uniform control; it should not automatically be read as a necessary factor in every loss or every minimax lower bound.

Upper Bounds for the Two Losses

The first step is a threshold argument that does not require differentiability. If \(\|\widehat f-f\|_\infty\leq\varepsilon\), a point classified differently from its true level-set status must have density value within \(\varepsilon\) of the threshold. Indeed, if \(f(x)\geq\lambda\) but \(\widehat f(x)<\lambda\), then \(f(x)<\lambda+\varepsilon\). If \(f(x)<\lambda\) but \(\widehat f(x)\geq\lambda\), then \(f(x)\geq\lambda-\varepsilon\). Therefore:

To see the conclusion, the two misclassification cases show \(L\triangle\widehat L\subseteq\{x:|f(x)-\lambda|\leq\varepsilon\}\). Taking probability and applying the margin condition proves the bound. In particular, a uniform density error of order \(\varepsilon_n\) gives symmetric-difference error of order \(\varepsilon_n^\alpha\), on the same high-probability event.

For Hausdorff loss, the uniform error must be paired with boundary geometry. Assume the boundary is compact and has a tubular neighborhood in which points can be written uniquely as \(z+s n(z)\), with \(z\in\partial L\), \(n(z)\) the unit normal pointing into \(L\), and signed coordinate \(s\). Assume throughout this neighborhood that moving inward increases \(f\) at rate at least \(g\), and moving outward decreases it at rate at least \(g\): for \(s\geq0\), \(f(z+s n(z))\geq\lambda+gs\), and for \(s\leq0\), \(f(z+s n(z))\leq\lambda+gs\). Also assume points outside this neighborhood are separated from the threshold by more than the error under consideration. These conditions rule out remote threshold regions that could invalidate a boundary-distance conclusion.

Here is the threshold detail that matters. At inward offset \(s=\varepsilon/g+\delta\), for any \(\delta>0\), the gradient condition gives \(f(z+s n(z))\geq\lambda+\varepsilon+g\delta\). Thus \(\widehat f(z+s n(z))\geq f(z+s n(z))-\varepsilon>\lambda\), so this point belongs to \(\widehat L\). Letting \(\delta\) decrease to zero bounds the distance from a boundary point of \(L\) to \(\widehat L\) by \(\varepsilon/g\). The strict inequality is important: at exactly \(s=\varepsilon/g\), the estimate is only guaranteed to be at least \(\lambda\), which does include the point, but an outward exclusion argument at the same offset would not be strict.

For the other directed distance, if \(x=z+s n(z)\) is outside \(L\) and belongs to \(\widehat L\), then \(\widehat f(x)\geq\lambda\), so \(f(x)\geq\lambda-\varepsilon\). Since \(s<0\) and \(f(x)\leq\lambda+gs\), it follows that \(s\geq-\varepsilon/g\). If \(x\) is inside \(L\) but outside \(\widehat L\), then \(\widehat f(x)<\lambda\), which implies \(f(x)<\lambda+\varepsilon\). For \(s\geq0\), the inward growth condition gives \(s<\varepsilon/g\). Together with the separation assumption away from the tube, these inequalities bound both directed distances, and hence the Hausdorff distance. This also makes clear why merely writing a non-strict inequality at the outward offset is not enough to prove exclusion from a set defined using \(\geq\lambda\).

Lower Bounds and the Meaning of “Minimax”

An upper bound describes a procedure; a minimax lower bound says that no procedure can uniformly do better over a specified class. The class matters. A smoothness index alone does not specify the boundary geometry, margin behavior, or the loss, so a rate should always be read together with its assumptions.

For regular boundaries, the familiar polynomial scale is \(n^{-\beta/(2\beta+d)}\). The following calculation explains why it appears. Consider a smooth baseline density with a boundary patch where the normal derivative is bounded above and below by positive constants. Use a smooth signed bump \(b\), supported in the unit-scale patch, with \(\int b(u)\,du=0\) and nonzero on a subpatch of the rescaled baseline boundary, and set \(f_\pm(x)=f_0(x)\pm a h^\beta b((x-x_0)/h)\). By change of variables each perturbation integrates to zero, so both alternatives have total mass one; since \(f_0\) is bounded below on the patch, sufficiently small fixed \(a>0\) keeps them nonnegative. The bump respects a Hölder-\(\beta\) bound. On the subpatch its value shifts the threshold by order \(a h^\beta\), so the baseline's normal derivative bounded above and below by positive constants implies a boundary displacement of order \(h^\beta\).

The squared perturbation integrated over its support is of order \(a^2 h^{2\beta+d}\). For the mass-preserving alternatives \(f_+\) and \(f_-\), bounded below on that support, their Kullback–Leibler divergence for \(n\) observations is at most a constant times \(n a^2 h^{2\beta+d}\). Choosing \(h=c n^{-1/(2\beta+d)}\) with \(c\) sufficiently small keeps this divergence bounded by a small constant. Le Cam’s two-point testing inequality then prevents reliable discrimination between the alternatives. For Hausdorff loss, their boundary displacement is order \(h^\beta\), giving a lower bound of order \(n^{-\beta/(2\beta+d)}\).

For symmetric difference under a regular boundary, place disjoint signed bumps on order \(h^{-(d-1)}\) boundary patches of tangential width \(h\), choosing each bump to have integral zero and to be nonzero on its boundary subpatch. Thus every hypercube alternative, indexed by the bump signs, retains total mass one; with sufficiently small \(a\), the alternatives remain nonnegative. Each patch contributes a symmetric-difference volume of order \(h^{d-1}h^\beta\). The one-coordinate testing difficulty is controlled by the same divergence \(n h^{2\beta+d}\). At the bandwidth above, each bit has error probability bounded away from zero; summing the expected losses across the order \(h^{-(d-1)}\) bits gives order \(h^{-(d-1)}h^{d-1}h^\beta=h^\beta\). Thus the regular-boundary symmetric-difference lower bound has polynomial order \(n^{-\beta/(2\beta+d)}\). This packing argument requires a class that actually contains such a baseline and disjoint local perturbations; it is not a consequence of the margin inequality alone.

For a general margin exponent \(\alpha\), the uniform-error argument gives the upper rate \((\log n/n)^{\alpha\beta/(2\beta+d)}\). A matching lower bound at polynomial order \(n^{-\alpha\beta/(2\beta+d)}\) requires a least-favorable family in the specified density class whose symmetric-difference separation and testing difficulty have the corresponding scaling. It cannot be asserted from the margin condition by itself. If that family is part of the assumptions, the exponents match up to logarithms; otherwise, report the proved upper rate and the lower bound actually available for that class.

Common Pitfalls and Practical Interpretation

• Using the same condition for both losses. The margin condition controls probability mass in a near-threshold band and yields a symmetric-difference bound. Hausdorff recovery needs spatial boundary control, such as a nonvanishing gradient and a suitable tubular neighborhood.
• Dropping the threshold convention. With \(\widehat L=\{\widehat f\geq\lambda\}\), equality belongs to the estimated set. To prove an outside point is excluded, use a strict inequality or a limiting distance argument; do not infer exclusion from \(\widehat f\leq\lambda\).
• Calling a plug-in upper bound minimax. A uniform density bound may introduce a logarithm. A lower bound without that logarithm establishes polynomial-order agreement, not an exact logarithmic minimax result.
• Ignoring the class behind the lower bound. A testing construction must remain inside the stated smoothness and geometric class. A margin exponent alone does not guarantee the alternatives needed for a matching lower bound.