Margin Conditions and Symmetric-Difference Rates

Why Density Error and Set Error Are Different

A plug-in level set is formed by thresholding an estimated density. Even when the density estimate is uniformly close to the truth, the estimated set can disagree with the true set wherever the density is close to the threshold. How much disagreement is possible therefore depends on the amount of space near that threshold, not only on the size of the density error.

The margin condition makes this idea quantitative. It bounds the volume of points whose density is within a small distance of the level \(\lambda\). Combined with a uniform error bound, it yields a direct bound on the volume of the symmetric difference between the two level sets.

Definition: Let \(\Omega\subseteq\mathbb{R}^d\) be measurable, let \(f:\Omega\to[0,\infty)\) be a density, and fix a threshold \(\lambda>0\). The true superlevel set is \(L_\lambda=\{x\in\Omega:f(x)\geq\lambda\}\). For a measurable function \(\hat f\), its plug-in level set is \(\hat L_\lambda=\{x\in\Omega:\hat f(x)\geq\lambda\}\). Write \(\mu\) for Lebesgue measure and \(A\triangle B=(A\setminus B)\cup(B\setminus A)\) for the symmetric difference.

For \(t>0\), the threshold band of width \(t\) is \(\{x\in\Omega:|f(x)-\lambda|\leq t\}\). Its volume measures how many locations could change sides of the threshold under a perturbation of size \(t\).

Definition: The density \(f\) satisfies a margin condition at level \(\lambda\) with parameters \(C>0\), \(\alpha>0\), and \(t_0>0\) if \[ \mu\{x\in\Omega:|f(x)-\lambda|\leq t\}\leq C t^\alpha \] for every \(0<t\leq t_0\). The exponent \(\alpha\) describes how quickly the volume near the threshold shrinks as the band narrows.

The Deterministic Conversion

The key fact is a set inclusion: if the estimated and true classifications disagree at a point, then the true density at that point must be close to the threshold. This requires no smoothness assumption; it follows directly from the uniform error.

Theorem: Suppose \(\sup_{x\in\Omega}|\hat f(x)-f(x)|\leq\delta\), where \(0<\delta\leq t_0\), and suppose \(f\) satisfies the margin condition at \(\lambda\). Then \[ \mu(\hat L_\lambda\triangle L_\lambda)\leq C\delta^\alpha. \]

Proof. Take any \(x\in\hat L_\lambda\triangle L_\lambda\). There are two cases. If \(f(x)\geq\lambda\) but \(\hat f(x)<\lambda\), then \[ 0\leq f(x)-\lambda < f(x)-\hat f(x)\leq\delta. \] If \(f(x)<\lambda\) but \(\hat f(x)\geq\lambda\), then \[ 0<\lambda-f(x)\leq\hat f(x)-f(x)\leq\delta. \] In either case, \(|f(x)-\lambda|\leq\delta\). Thus \[ \hat L_\lambda\triangle L_\lambda \subseteq \{x\in\Omega:|f(x)-\lambda|\leq\delta\}. \] Taking Lebesgue measures and applying the margin condition at \(t=\delta\) gives \[ \mu(\hat L_\lambda\triangle L_\lambda) \leq\mu\{x:|f(x)-\lambda|\leq\delta\} \leq C\delta^\alpha. \] \(\square\)

This is a deterministic statement: it holds for every estimated function satisfying the stated uniform error bound. In particular, it quantifies the symmetric-difference volume without requiring a separate geometric description of the boundary.

Worked Example: A Normalized Estimate and a Shifted Boundary

Let \(\Omega=[0,1]\), \(f(x)=2x\), and \(\lambda=1\). The function \(f\) is a density since it is nonnegative and \(\int_0^1 2x\,dx=1\). The true level set is \(L_1=[1/2,1]\). Consider the density estimate \[ \hat f(x)=2x+\frac{25}{193}(1-3x^2). \]

Check that \(\hat f\) is a density. The perturbation integrates to zero: \[ \int_0^1(1-3x^2)\,dx=1-1=0, \] so \(\int_0^1\hat f(x)\,dx=1\). Also, \[ \hat f'(x)=2-\frac{150}{193}x\geq 2-\frac{150}{193}=\frac{236}{193}>0 \] on \([0,1]\), and \(\hat f(0)=25/193>0\). Hence \(\hat f\) is nonnegative and increasing.

Find the estimated boundary. At \(x=0.48=12/25\), \[ 1-3x^2=1-\frac{432}{625}=\frac{193}{625}, \qquad \frac{25}{193}(1-3x^2)=\frac{1}{25}=0.04. \] Therefore \(\hat f(0.48)=0.96+0.04=1\). Since \(\hat f\) is increasing, \(\hat L_1=[0.48,1]\). Consequently, \[ \hat L_1\triangle L_1=[0.48,0.5) \quad\text{and}\quad \mu(\hat L_1\triangle L_1)=0.5-0.48=0.02. \]

Check the bound. For \(0<t\leq1\), the band around the true threshold satisfies \[ |2x-1|\leq t \quad\Longleftrightarrow\quad \frac{1-t}{2}\leq x\leq\frac{1+t}{2}. \] Its length is \(t\), so the margin condition holds with \(C=1\), \(\alpha=1\), and \(t_0=1\). The uniform error is \[ \|\hat f-f\|_\infty =\frac{25}{193}\max_{0\leq x\leq1}|1-3x^2| =\frac{50}{193}. \] The theorem gives a bound of \(50/193\), which is larger than the actual symmetric-difference volume \(0.02\), as it must be.

How the Margin Exponent Changes the Rate

If the margin exponent is large, little volume lies near the threshold, and a small uniform error produces a particularly small set error. If the exponent is small, the threshold band contracts more slowly, so uniform accuracy translates into a weaker set rate. The exponent is a property of the density near the chosen level, not a universal constant shared by all thresholds.

Worked Example: A Threshold Boundary at 0.98

Let \(f(x)=2(1-x)\) on \([0,1]\), a density because \(\int_0^1 2(1-x)\,dx=1\), and take \(\lambda=0.04\). Solving for the boundary gives \[ 2(1-x)=0.04 \quad\Longrightarrow\quad x=1-\frac{0.04}{2}=0.98. \] Thus the true level set is \([0,0.98]\). The boundary is \(0.98\), not \(0.48\).

For \(0<t\leq0.04\), the band around the threshold is determined by \[ 0.04-t\leq2(1-x)\leq0.04+t. \] Solving both inequalities gives \[ 0.98-\frac{t}{2}\leq x\leq0.98+\frac{t}{2}. \] This interval lies in \([0,1]\) for the stated range of \(t\), and its length is \(t\). The margin condition therefore holds with \(C=1\), \(\alpha=1\), and \(t_0=0.04\). If a plug-in estimate has uniform error at most \(0.01\), the theorem bounds the symmetric-difference volume by \(0.01\).

A different local shape can produce a different exponent. For example, near a flat maximum the density can approach the threshold quadratically. Then the threshold band can have volume proportional to the square root of its width, corresponding to \(\alpha=1/2\). The next example verifies this calculation.

Worked Example: A Quadratic Maximum and a Half-Power Margin

On \([-1,1]\), let \(f(x)=\frac{3}{4}(1-x^2)\) and take \(\lambda=3/4\). The density integrates to one because \[ \int_{-1}^{1}\frac{3}{4}(1-x^2)\,dx =\frac{3}{4}\left(2-\frac{2}{3}\right)=1. \] The level set at the maximum is \(L_\lambda=\{0\}\).

For \(0<t\leq3/4\), \[ \left|f(x)-\frac{3}{4}\right| =\frac{3}{4}x^2\leq t \quad\Longleftrightarrow\quad |x|\leq\sqrt{\frac{4t}{3}}. \] The band has length \(2\sqrt{4t/3}=4\sqrt{t/3}\). Hence this density satisfies the margin condition with \(\alpha=1/2\), \(C=4/\sqrt{3}\), and \(t_0=3/4\). A uniform error \(\delta\leq3/4\) therefore yields \[ \mu(\hat L_\lambda\triangle L_\lambda) \leq\frac{4}{\sqrt{3}}\delta^{1/2}. \] The square-root rate is slower than a linear rate for small \(\delta\); for example, \(\delta^{1/2}>\delta\) whenever \(0<\delta<1\).

From a Uniform Estimation Rate to a Set Rate

The deterministic result applies to random density estimates by applying it on events where their uniform error is small. Write \(\Delta_n=\sup_{x\in\Omega}|\hat f_n(x)-f(x)|\), and assume \(\Delta_n\) is measurable. The notation \(\Delta_n=O_p(r_n)\) means that for every \(\varepsilon>0\), there is a finite \(M\) such that \(P(\Delta_n>Mr_n)<\varepsilon\) for all sufficiently large \(n\).

Rate consequence: Suppose \(r_n\to0\), \(\Delta_n=O_p(r_n)\), and the margin condition holds with fixed \(C,\alpha,t_0\). Then \[ \mu(\hat L_{\lambda,n}\triangle L_\lambda)=O_p(r_n^\alpha). \]

Proof. Since \(r_n\to0\) and \(\Delta_n=O_p(r_n)\), we have \(P(\Delta_n\leq t_0)\to1\). On this event the deterministic theorem gives \[ \mu(\hat L_{\lambda,n}\triangle L_\lambda)\leq C\Delta_n^\alpha. \] Also \(\Delta_n^\alpha=O_p(r_n^\alpha)\): for any \(\varepsilon>0\), choose \(M\) so that \(\Delta_n\leq Mr_n\) with probability at least \(1-\varepsilon\) for all sufficiently large \(n\); then \(\Delta_n^\alpha\leq M^\alpha r_n^\alpha\) on that event. The event \(\Delta_n>t_0\) has probability tending to zero, so it does not change this bounded-in-probability rate. This proves the claim. \(\square\)

Worked Example: Translating a Stochastic Uniform Rate

Suppose the density \(f(x)=2x\) on \([0,1]\) is thresholded at \(\lambda=1\), so its margin condition has \(C=1\) and \(\alpha=1\). Assume a sequence of estimates satisfies \[ \|\hat f_n-f\|_\infty=O_p(n^{-1/3}). \] The rate consequence gives \[ \mu(\hat L_{1,n}\triangle L_1)=O_p\bigl((n^{-1/3})^1\bigr) =O_p(n^{-1/3}). \] If instead the relevant margin exponent were \(1/2\), the same uniform density rate would imply a set-volume rate \(O_p(n^{-1/6})\), since \((n^{-1/3})^{1/2}=n^{-1/6}\). The uniform estimation rate alone does not determine the set rate; the margin exponent matters.

Volume Loss, Probability Loss, and a Common Pitfall

The symmetric-difference volume is not the same as the probability mass of disagreement under the distribution with density \(f\). That probability loss is \[ P_X(\hat L_\lambda\triangle L_\lambda) =\int_{\hat L_\lambda\triangle L_\lambda}f(x)\,dx. \] If \(f\) is bounded above by \(M_f\), then it is at most \(M_f\mu(\hat L_\lambda\triangle L_\lambda)\), so the volume rate also gives a probability-loss rate. Without such a bound, a volume bound alone need not control probability mass at the same scale.

Common mistake: It is tempting to argue that a uniform density error of \(\delta\) always gives a symmetric-difference volume of order \(\delta\). That conclusion ignores how much space may have density near \(\lambda\). The correct general implication is \(C\delta^\alpha\) under the stated margin condition. For example, the quadratic-maximum calculation above has \(\alpha=1/2\), not \(1\).

A second pitfall is to infer an expected loss rate directly from an \(O_p\) statement. Boundedness in probability controls the error with high probability, but does not by itself control the contribution of rare, very large errors to an expectation. An expected-rate claim needs additional tail or moment control, as well as appropriate control of the loss on the exceptional event.

Key takeaway: Uniform density error \(\delta\) places every disagreement inside a threshold band of width \(\delta\). A margin condition bounds that band’s volume by \(C\delta^\alpha\), and consequently converts a stochastic uniform rate \(r_n\) into a symmetric-difference rate \(r_n^\alpha\).

Check Your Understanding

Use the definitions and results above to answer these questions.

State the margin condition at level \(\lambda\) and explain what the exponent \(\alpha\) controls.
Why must every point in the symmetric difference lie in the threshold band whose width is the uniform error?
If the uniform error is \(O_p(n^{-2/5})\) and the margin exponent is \(1/2\), what symmetric-difference volume rate follows?
For \(f(x)=2(1-x)\) and \(\lambda=0.04\), verify the level-set boundary and explain why the band has length \(t\) for \(0<t\leq0.04\).
What additional condition would allow a volume rate to imply the same order of probability-mass loss?