Bump-Function Lower Bounds for Density Estimation

Why Lower Bounds Use Local Alternatives

An estimator can have small integrated squared error only if it can distinguish densities that are close as probability distributions. A useful way to test that limitation is to build many densities that agree almost everywhere but differ by small, localized perturbations. Each perturbation contributes a definite amount to squared-error loss; if the data cannot reliably reveal its sign, that contribution cannot be avoided.

This tutorial develops that argument for densities on $[0,1]$. It constructs smooth alternatives, bounds the distance between the sampling distributions they induce, and proves how testing errors force integrated squared-error risk. The result is a lower-bound technique; it does not by itself provide a matching estimator or establish a complete minimax comparison.

Definition: For a density estimator $\hat f$ based on $n$ independent observations, its integrated squared-error loss at density $f$ is $$ \|\hat f-f\|_2^2=\int_0^1\{\hat f(x)-f(x)\}^2\,dx. $$ The risk is the expectation of this loss under the sampling distribution generated by $f$. We consider estimators that are measurable as $L_2([0,1])$-valued functions; an estimator with infinite squared error only makes a lower bound immediate.

Building Smooth, Normalized Alternatives

Fix a smoothness exponent $\beta>0$, and write $\beta=m+\alpha$, where $m$ is a nonnegative integer and $0<\alpha\leq1$. For integer $\beta$, use $m=\beta-1$ and $\alpha=1$. A Hölder class of order $\beta$ bounds derivatives through order $m$ and requires the $m$th derivative to be $\alpha$-Hölder continuous. The class also imposes a fixed bound $L$ on these quantities. We take $L$ large enough to contain the uniform density and the perturbations below.

Choose a nonzero, infinitely differentiable function $\psi$ supported on $[-1/2,1/2]$ with zero integral. One explicit choice is $\psi=\phi'$, where $$ \phi(t)= \begin{cases} \exp\{-1/(1-4t^2)\},& |t|<1/2,\\ 0,& |t|\geq 1/2. \end{cases} $$ The function $\phi$ and all its derivatives vanish at the support boundary. Thus $\psi$ is smooth, nonzero, compactly supported, and $\int\psi(t)\,dt=0$, by the fundamental theorem of calculus. Write $B=\|\psi\|_\infty$ and $Q=\int\psi(t)^2\,dt$, both finite, with $Q>0$.

For a width $h\leq1$, put $M=\lfloor1/h\rfloor$, and place one bump in each of the first $M$ adjacent intervals of length $h$. Define $$ \psi_j(x)=\psi\!\left(\frac{x-(j-\tfrac12)h}{h}\right),\qquad j=1,\ldots,M. $$ Their supports have disjoint interiors. For a sign vector $\theta=(\theta_1,\ldots,\theta_M)\in\{-1,1\}^M$, set $$ f_\theta(x)=1+a\sum_{j=1}^M\theta_j\psi_j(x),\qquad a=c h^\beta, $$ where $c>0$ is a sufficiently small constant.

Construction result: For $c$ sufficiently small, every $f_\theta$ is a density in the chosen Hölder class of order $\beta$. Each alternative has the same baseline density $1$, with a choice of sign for each localized bump.

To check normalization, change variables within each support: $$ \int_0^1\psi_j(x)\,dx=h\int_{-1/2}^{1/2}\psi(t)\,dt=0. $$ Therefore $\int_0^1 f_\theta(x)\,dx=1$. At any point, at most one bump is nonzero, so $f_\theta(x)\geq1-aB$. Since $h\leq1$, choosing $cB\leq1/2$ ensures $f_\theta(x)\geq1/2$.

For smoothness, the derivative of order $r\leq m$ of a bump term has size at most $c h^{\beta-r}\|\psi^{(r)}\|_\infty$. These quantities are uniformly bounded for $h\leq1$. The scaling of the order-$m$ derivative gives an $\alpha$-Hölder bound proportional to $c h^{\beta-m-\alpha}=c$. The compactly supported derivatives vanish at cell boundaries, so adjacent cells do not create jumps; the Hölder bound across a boundary is controlled by the same scaled bump bounds. Taking $c$ small enough, depending on $L,\beta,\psi$, keeps the alternatives in the class.

Worked Example: Four Normalized Bumps

Take $h=1/4$, $M=4$, and $\beta=1$. The four bump supports occupy the four adjacent quarter-intervals of $[0,1]$. For any $\theta\in\{-1,1\}^4$, define $f_\theta(x)=1+c h\sum_{j=1}^4\theta_j\psi_j(x)$.

Each bump has integral $(1/4)\int\psi=0$, so the integral of $f_\theta$ is $1$. At every $x$, at most one bump contributes; hence $f_\theta(x)\geq1-cB/4$. If $cB\leq1/2$, then $f_\theta(x)\geq7/8$, in particular it is nonnegative. Its integral and nonnegativity verify that it is a density. For $\beta=1$, the first derivative of each perturbation is $c\psi'((x-(j-\tfrac12)h)/h)$; its magnitude is bounded by $c\|\psi'\|_\infty$, independent of the quarter-interval width. A sufficiently small $c$ therefore also satisfies a fixed Lipschitz smoothness bound.

How Hard Are Neighboring Alternatives to Distinguish?

Two sign vectors are neighbors if they differ in exactly one coordinate, say $j$. Their densities differ by $2a\psi_j$, so $$ \int_0^1\{f_\theta(x)-f_{\theta'}(x)\}^2\,dx =4a^2hQ. $$ This is the squared $L_2$ separation. The corresponding sampling distributions can nevertheless be close when the perturbation is small.

For probability densities $p,q$ with $q>0$, define the chi-square divergence by $\chi^2(p,q)=\int(p-q)^2/q$, and total variation distance by $\operatorname{TV}(p,q)=\tfrac12\int|p-q|$. Cauchy–Schwarz gives $\operatorname{TV}(p,q)\leq\tfrac12\sqrt{\chi^2(p,q)}$. For $n$ independent observations, the product distributions satisfy $$ 1+\chi^2(p^{\otimes n},q^{\otimes n})=\{1+\chi^2(p,q)\}^n. $$ Indeed, under $q$, the likelihood ratio $p/q$ has expectation $1$ and second moment $1+\chi^2(p,q)$; independence multiplies second moments.

For neighboring alternatives, $q\geq1/2$ and their density difference is $2a\psi_j$. Thus $$ \chi^2(f_\theta,f_{\theta'}) \leq 2\int_0^1(f_\theta-f_{\theta'})^2 =8a^2hQ. $$ Using $(1+u)^n\leq e^{nu}$ for $u\geq0$, if $8na^2hQ\leq\log(5/4)$, then the product chi-square divergence is at most $1/4$. The total variation distance between the two $n$-sample distributions is consequently at most $1/4$.

Worked Example: Choosing a Width for a Testing Bound

Let $a=ch^\beta$, and choose $$ h=\left\{\frac{\log(5/4)}{8nc^2Q}\right\}^{1/(2\beta+1)} $$ whenever this value is at most $1$. Substitution gives $8na^2hQ=8nc^2h^{2\beta+1}Q=\log(5/4)$. For any neighboring pair, the one-observation chi-square divergence is at most $8c^2h^{2\beta+1}Q$. Therefore $$ \chi^2(f_\theta^{\otimes n},f_{\theta'}^{\otimes n}) \leq \exp\{8nc^2h^{2\beta+1}Q\}-1 =\frac54-1=\frac14. $$ Applying the stated total variation inequality gives a bound of $\tfrac12\sqrt{1/4}=1/4$. Thus, for this width, no test can distinguish any neighboring pair with total variation exceeding $1/4$. The small-width condition is explicit; for fixed $c,Q,\beta$, it holds for all sufficiently large $n$.

Turning Testing Errors into Integrated Squared Error

The key step is to turn any density estimate into guesses about the bump signs. Let $e_j=\psi_j/\sqrt{hQ}$; disjoint supports make these functions orthonormal in $L_2([0,1])$. The coefficient of $f_\theta-1$ along $e_j$ is $\theta_j a\sqrt{hQ}$. Given an estimator $\hat f$, let $b_j=\langle\hat f-1,e_j\rangle$, and guess $+1$ when $b_j\geq0$, $-1$ otherwise. If this guess is wrong, then $$ |b_j-\theta_j a\sqrt{hQ}|\geq a\sqrt{hQ}. $$ By orthonormality, the sum of squared coefficient errors is no greater than the full squared $L_2$ error.

Theorem: Suppose all alternatives $f_\theta$ belong to the density class and every neighboring pair has $n$-sample total variation distance at most $1/4$. Then every estimator $\hat f$ satisfies $$ \sup_{\theta\in\{-1,1\}^M} E_{f_\theta}\|\hat f-f_\theta\|_2^2 \geq \frac{3}{8}M a^2hQ. $$

Proof. Fix a coordinate $j$ and pair each sign vector with the vector obtained by flipping its $j$th sign. For any decision rule between two distributions $P_+$ and $P_-$, the sum of its two error probabilities is at least $1-\operatorname{TV}(P_+,P_-)$. To see this, if $A$ is the event that the rule chooses $+$, the sum is $P_+(A^c)+P_-(A)=1-\{P_+(A)-P_-(A)\}$, which is at least $1-\operatorname{TV}(P_+,P_-)$. Thus each paired average error probability is at least $(1-1/4)/2=3/8$. Averaging uniformly over all sign vectors, the probability of an incorrect guess for each coordinate is at least $3/8$.

For each data set, orthonormality gives $$ \|\hat f-f_\theta\|_2^2 \geq\sum_{j=1}^M\left\langle\hat f-f_\theta,e_j\right\rangle^2. $$ Whenever the $j$th guess is wrong, its summand is at least $a^2hQ$. Average this inequality over the uniform distribution on sign vectors and over the data. The average risk is at least $M a^2hQ(3/8)$. The supremum risk is at least the average risk, proving the claim. $\square$

Worked Example: Two Bumps and the Risk Contribution

Suppose $M=2$ and the neighboring $n$-sample distributions have total variation at most $1/4$. For each of the two bump signs, the average probability of a wrong guess over the paired alternatives is at least $3/8$. A wrong guess for one sign contributes at least $a^2hQ$ to squared error. Adding the two coordinates gives the lower bound $$ 2\left(\frac38\right)a^2hQ=\frac34a^2hQ. $$ This is a bound on the average risk over the four sign vectors, and therefore also a bound on the largest risk among those four alternatives. It does not rely on an estimator being a density: the coefficient argument applies to any $L_2$-valued estimator.

What the Bound Says—and a Common Pitfall

The construction identifies two quantities that must be balanced. Each bump has squared $L_2$ size $a^2hQ=c^2h^{2\beta+1}Q$, while about $1/h$ disjoint bumps fit on the interval. The testing condition keeps neighboring data distributions close; the theorem then sums the unavoidable errors across the coordinates. For the width used in the testing example, $M=\lfloor1/h\rfloor$ is at least $1/(2h)$ when $h\leq1$. The theorem consequently gives a lower bound of at least $(3/16)c^2Qh^{2\beta}$. This illustrates how the construction produces a risk lower bound from smoothness and distinguishability; upper bounds and rate comparisons require a separate analysis.

A common mistake is to use arbitrary positive bumps and assume that their sum preserves the density normalization. In general it does not: a positive bump adds mass. Here every perturbation has exactly zero integral, so changing its sign leaves total mass unchanged. A second pitfall is to confuse $L_2$ separation of densities with statistical distinguishability. The proof needs both calculations: bump separation quantifies the loss from a wrong sign, while a testing-distance bound shows that such a sign error cannot always be prevented.

Key takeaway: Place zero-integral smooth bumps on disjoint intervals, scale their amplitudes to stay in the density class, and choose their width so neighboring sampling distributions remain close. Orthogonal bump signs then convert testing errors into a lower bound for integrated squared-error risk.

Check Your Understanding

Use the construction and argument above to answer these questions.

Why does a zero-integral bump preserve the total mass of each density alternative?
For neighboring alternatives, why is their squared $L_2$ separation $4a^2hQ$, rather than $a^2hQ$?
What condition on the one-observation chi-square divergence ensures that the $n$-sample total variation distance is at most $1/4$ in this argument?
Explain why an incorrect sign guess forces a squared coefficient error of at least $a^2hQ$.
Why does a lower bound on average risk over the sign vectors imply a lower bound on the largest risk among them?