The Sandwich Bound for Estimated Level Sets

Why a Uniform Error Bound Gives a Set Sandwich

A density estimate is often used by thresholding: include a point when its estimated density is at least a chosen level. The resulting set can differ from the population set because the estimated density is not exact. A uniform error bound gives a direct way to control that difference. It says that every estimated inclusion must be compatible with the true density being no more than a specified amount below the threshold, and every point sufficiently above the threshold must be included by the estimate.

This is a deterministic implication: once the error bound holds, the set inclusions follow without a probability calculation. If the estimate is random, the same implication holds on every outcome for which the uniform bound holds. The guarantee concerns containment between sets, not equality of their boundaries or closeness of their shapes.

The use of \(\ge\) is part of the convention: points exactly at the threshold belong to the superlevel set. The pointwise form of the error bound matters too. If the available guarantee is only an essential-supremum bound, then the pointwise argument below applies outside a set of Lebesgue measure zero; it does not necessarily give inclusion at every point. We first state and prove the pointwise version.

The Sandwich Theorem

The two inclusions have different roles. The inner population set contains points whose true density is high enough that even a downward estimation error of size \(\varepsilon\) leaves the estimate at or above \(\lambda\). The outer population set contains every point that could reach the estimated threshold despite an upward error of that size.

Proof. Take any \(x\in L_f(\lambda+\varepsilon)\). By definition, \(f(x)\ge\lambda+\varepsilon\). The error bound implies \(\hat f(x)\ge f(x)-\varepsilon\), so \(\hat f(x)\ge\lambda\). Thus \(x\in L_{\hat f}(\lambda)\), proving the first inclusion. Now take any \(x\in L_{\hat f}(\lambda)\). Then \(\hat f(x)\ge\lambda\), and the error bound implies \(f(x)\ge\hat f(x)-\varepsilon\ge\lambda-\varepsilon\). Hence \(x\in L_f(\lambda-\varepsilon)\), proving the second inclusion. \(\square\)

The non-strict inequalities are important. At the lower edge of the estimated set, the estimate may equal \(\lambda\); at the upper edge of the inner population set, the true density may equal \(\lambda+\varepsilon\). Both points are included under the stated convention, and the proof still applies exactly.

Membership Consequences and a Disagreement Band

The sandwich can also locate every point on which the estimated and population sets disagree at the original threshold. Write \(A=L_f(\lambda)\) and \(\hat A=L_{\hat f}(\lambda)\). If a point belongs to exactly one of these sets, its true density must be near \(\lambda\): far above the threshold it is included by both, and far below it is excluded by both.

Proof. First suppose \(x\in A\setminus\hat A\). Then \(f(x)\ge\lambda\), while \(\hat f(x)<\lambda\). Since \(f(x)\le\hat f(x)+\varepsilon\), it follows that \(f(x)<\lambda+\varepsilon\). Thus \(\lambda\le f(x)<\lambda+\varepsilon\). Next suppose \(x\in\hat A\setminus A\). Then \(\hat f(x)\ge\lambda\), while \(f(x)<\lambda\). Since \(f(x)\ge\hat f(x)-\varepsilon\), it follows that \(f(x)\ge\lambda-\varepsilon\). Thus \(\lambda-\varepsilon\le f(x)<\lambda\). Both cases place \(x\) in the displayed band, proving the result. \(\square\)

The band’s endpoints reflect the threshold convention. A point with \(f(x)=\lambda-\varepsilon\) can be included by the estimate if its error is upward by exactly \(\varepsilon\), so the lower endpoint is included. A point with \(f(x)=\lambda+\varepsilon\) cannot be omitted by the estimate under the assumed bound, so the upper endpoint is excluded from the disagreement band.

Endpoint Behavior and What the Bound Does Not Say

The shifted levels cannot in general be tightened using only the uniform error bound. The next example checks both boundary cases with valid densities. It also illustrates why the sandwich is not an equality: the estimate may include points that are below the target population level, provided they remain within the uncertainty allowed by \(\varepsilon\).

A frequent mistake is to read the theorem as saying that the estimated set equals the population set, or that every point in the outer set must be estimated as included. The proof gives only the two stated containments. In the example above, every point in \([0,1]\) is estimated as included, although most points do not belong to \(L_f(1.2)\). Reversing either inclusion is also unjustified: the error bound does not say that every point of \(L_f(\lambda-\varepsilon)\) is estimated above \(\lambda\), or that every estimated point has true density at least \(\lambda+\varepsilon\).