From a Density Estimate to a Set Estimate
A density level set describes the locations where a distribution is sufficiently concentrated. It is often used to identify a high-density region or to summarize the shape of a distribution. In practice, the density is unknown, so the region must be constructed from an estimate. This is a plug-in procedure: estimate the density, then apply the same threshold rule used to define the target set.
The resulting set can differ from the target for two distinct reasons. The estimated density may place some points on the wrong side of the threshold, and the threshold itself may differ from the target threshold. Separating these effects makes it possible to describe what a set-error bound must control without conflating density accuracy with threshold choice.
The threshold \(\hat\tau\) may be fixed at \(\tau\), or it may be estimated from the data. The definition requires the estimated function and threshold to be measurable so that the resulting sets are measurable. The arguments below hold for every realized pair \((\hat f_n,\hat\tau)\); no independence between them is required.
To measure set error, let \(\mu\) be a finite measure on \(\mathbb{R}^d\). For example, \(\mu\) might be Lebesgue measure when comparing geometric size, or the distribution \(P_X\) of a new observation when measuring probability mass. Write \(d_\mu(A,B)=\mu(A\triangle B)\), where \(A\triangle B=(A\setminus B)\cup(B\setminus A)\) is the symmetric difference. This loss counts the measure of points whose membership differs.
The Two Components of Set Error
Introduce an intermediate set: threshold the estimated density at the true threshold. Comparing this set with the target isolates the effect of density estimation. Comparing it with the final plug-in set isolates the effect of changing the threshold while holding the estimated density fixed.
Proof. For any three sets \(A,B,C\), a point in \(A\triangle C\) must belong to \(A\triangle B\) or to \(B\triangle C\). Indeed, if its membership in \(A\) and \(C\) differs, its membership cannot agree with both \(B\) and \(A\), and with \(B\) and \(C\). Therefore \(\mathbf{1}_{A\triangle C}\leq \mathbf{1}_{A\triangle B}+\mathbf{1}_{B\triangle C}\) pointwise. Integrating with respect to \(\mu\) gives \(d_\mu(A,C)\leq d_\mu(A,B)+d_\mu(B,C)\). Taking \(A=L(\tau)\), \(B=\hat L_n(\tau)\), and \(C=\hat L_n(\hat\tau)\) proves the claim. \(\square\)
This is an upper bound, not generally an equality. The two component errors can overlap: a point misclassified by the density-only set can become correctly classified after the threshold changes. Consequently, adding the component errors can overstate the final set error.
Worked Example: Threshold Error With an Exact Density
Let \(f(x)=(1-|x|)_+\) on the real line, where \(u_+=\max(u,0)\). This is a density: it is nonnegative and its integral is \(2\int_0^1(1-x)\,dx=1\). Take the target threshold \(\tau=0.5\), suppose \(\hat f_n=f\), and use \(\hat\tau=0.4\).
The target set satisfies \(1-|x|\geq0.5\), so \(L(0.5)=[-0.5,0.5]\). The estimated set satisfies \(1-|x|\geq0.4\), so \(\hat L_n(0.4)=[-0.6,0.6]\). With Lebesgue measure, their symmetric difference has length \(0.1+0.1=0.2\). The density component is zero because \(\hat f_n=f\); all the error comes from the threshold component.
If instead error is measured by the true probability \(P_X\), the two extra intervals have total probability $$ 2\int_{0.5}^{0.6}(1-x)\,dx =2\left[(x-x^2/2)\big|_{0.5}^{0.6}\right] =2(0.420-0.375)=0.09. $$ Thus the same set discrepancy has Lebesgue measure \(0.2\) but probability mass \(0.09\), illustrating why the measure used for set loss must be stated.
Worked Example: Density Error With a Fixed Threshold
Use the same true density \(f(x)=(1-|x|)_+\) and threshold \(\tau=\hat\tau=0.5\). Consider the shifted density estimate \(\hat f_n(x)=(1-|x-0.1|)_+\). It is a density because it is a translate of \(f\). Its level set at \(0.5\) is \([-0.4,0.6]\), whereas the target set is \([-0.5,0.5]\).
The symmetric difference consists of \([-0.5,-0.4)\) and \((0.5,0.6]\), up to endpoints, so its Lebesgue measure is \(0.1+0.1=0.2\). The threshold component is zero because the thresholds agree; the entire discrepancy is the density component.
Under the true distribution, the two pieces have probabilities $$ \int_{-0.5}^{-0.4}(1+x)\,dx=0.055, \qquad \int_{0.5}^{0.6}(1-x)\,dx=0.045. $$ Their sum is \(0.1\). Although the density estimate is uniformly close to the true density—the shift is \(0.1\), and the positive-part triangular function is 1-Lipschitz—the set still changes on intervals with positive length.
A Pointwise Bound on Disagreement
The component decomposition measures set errors directly. A complementary calculation explains which points can be misclassified. At a point \(x\), define the true and estimated threshold scores by \(f(x)-\tau\) and \(\hat f_n(x)-\hat\tau\). Membership is determined by whether the corresponding score is nonnegative.
Proof. Let \(a=f(x)-\tau\) and \(b=\hat f_n(x)-\hat\tau\). If membership differs, one score is nonnegative and the other is negative. If \(a\geq0>b\), then \(|a|=a\leq a-b=|a-b|\). If \(b\geq0>a\), then \(|a|=-a\leq b-a=|a-b|\). Thus in either case \(|a|\leq|a-b|\). Also, $$ |a-b| =|(f(x)-\hat f_n(x))+(\hat\tau-\tau)| \leq |f(x)-\hat f_n(x)|+|\hat\tau-\tau|, $$ by the triangle inequality. This proves the pointwise claim. Integrating the resulting indicator inequality with respect to \(\mu\) gives the set-error bound. \(\square\)
If the density error is uniformly bounded by \(\varepsilon\), meaning \(\sup_x|f(x)-\hat f_n(x)|\leq\varepsilon\), the bound simplifies to $$ d_\mu\!\left(L(\tau),\hat L_n(\hat\tau)\right) \leq \mu\!\left(\{x:|f(x)-\tau|\leq\varepsilon+|\hat\tau-\tau|\}\right). $$ This says that disagreement can occur only where the true density is close enough to the threshold to be affected by the combined score error. It does not say that this region has small measure: that depends on how much \(\mu\)-mass lies near the threshold.
Worked Example: Both Error Sources, With Overlap
Keep the triangular true density \(f(x)=(1-|x|)_+\) and \(\tau=0.5\). Use the shifted estimate \(\hat f_n(x)=(1-|x-0.1|)_+\), but now set \(\hat\tau=0.4\). The target set is \([-0.5,0.5]\). At the true threshold, the estimated density gives \(\hat L_n(0.5)=[-0.4,0.6]\); at the estimated threshold, it gives \(\hat L_n(0.4)=[-0.5,0.7]\).
With Lebesgue measure, the density component is \(d(L(0.5),\hat L_n(0.5))=0.1+0.1=0.2\). The threshold component is \(d(\hat L_n(0.5),\hat L_n(0.4))=0.1\), from the added interval \((0.6,0.7]\). The decomposition therefore gives an upper bound of \(0.2+0.1=0.3\). The actual target-to-final discrepancy is only the interval \((0.5,0.7]\), of length \(0.2\): part of the intermediate-set error has disappeared. This verifies why the decomposition is an inequality rather than an additive identity.
Interpreting the Error and Avoiding a Common Mistake
The two results answer related but different questions. The set-error decomposition identifies a density-only comparison and a threshold-only comparison. The score-error bound explains why points far from the true threshold are resistant to small perturbations: their membership cannot change unless the combined density and threshold error is large enough. Neither result, by itself, supplies a rate of convergence. To turn a density-error bound into a small set error, one also needs control of the measure near the threshold.
- Mistake: treating a small threshold error as a small set error. The reasoning “\(|\hat\tau-\tau|\) is small, so the sets are close” ignores density error and the amount of mass near the threshold. In the shifted-density example, the thresholds agree exactly, yet the sets differ.
- Correction: Track the density and threshold contributions separately, and state the measure used to quantify set discrepancy.
- Mistake: treating a small uniform density error as sufficient by itself. Small score perturbations restrict disagreement to points near the threshold, but do not guarantee that the near-threshold region has small measure.
- Correction: Use the score-error bound to identify the region where disagreement is possible; assessing its measure requires additional information about the distribution of density values near \(\tau\).
Check Your Understanding
Use the definitions and results above to answer the following.
- For a fixed density estimate, which term in the set-error decomposition vanishes when \(\hat\tau=\tau\)?
- Why is the set-error decomposition an inequality rather than an identity in general?
- State the condition on the two threshold scores that must hold for a point to be in the symmetric difference.
- If \(\sup_x|f(x)-\hat f_n(x)|\leq0.03\) and \(|\hat\tau-\tau|=0.02\), what condition must a disagreeing point satisfy in terms of \(|f(x)-\tau|\)?
- Why can two set discrepancies have different numerical values under Lebesgue measure and under \(P_X\)?