Two-Point Lower Bounds From Local Perturbations

Why Compare Two Regression Functions?

A lower bound for estimation can be obtained by finding two regression functions that are separated in integrated squared error but whose data distributions are difficult to distinguish. If an estimator cannot reliably tell which function generated the observations, it cannot be close to both functions at once. The key is to quantify both parts of this argument: the functions’ separation and the difficulty of the associated testing problem.

Here the perturbation is localized: it has a small support and its height is constrained by Hölder smoothness. That localization determines both its squared-error contribution and the information it leaves in the data. A careful calculation matters. In particular, a single localized bump yields a valid lower bound, but its order is not the sharp integrated-risk rate in general.

Regression Model and Localized Perturbation

Assume the observations \((X_i,Y_i)\), \(i=1,\ldots,n\), are independent and identically distributed according to \(X_i\sim\operatorname{Unif}([0,1]^d)\) and \(Y_i=f(X_i)+\varepsilon_i\), where the errors are independent of the design and satisfy \(\varepsilon_i\sim N(0,\sigma^2)\) with \(\sigma^2>0\). Write \(P_f\) and \(E_f\) for probability and expectation under the joint distribution of the data when the regression function is \(f\). The loss considered here is integrated squared error with respect to Lebesgue measure on \([0,1]^d\).

Fix a nonzero \(C^\infty\) function \(\psi:\mathbb R^d\to\mathbb R\) supported on \([-1,1]^d\), and choose \(x_0=(1/2,\ldots,1/2)\). For \(0<h\leq 1/2\) and amplitude \(a>0\), define \(f_0(x)=0\) and \(f_1(x)=a h^\beta\psi((x-x_0)/h)\). The support of \(f_1\) lies in the domain. For sufficiently small fixed \(a\), these functions belong to \(\mathcal H^\beta(L)\) for every such \(h\). Indeed, a derivative of order \(j\) scales as \(a h^{\beta-j}\); for \(j\leq\beta\) in the integer case this is bounded uniformly for \(h\leq1\). In the noninteger case, the order-\(m\) Hölder seminorm scales as \(a h^{\beta-m-\alpha}=a\). The fixed bump has finite derivative bounds and seminorms, so choosing \(a\) small enough meets the ball’s radius.

Let \(I_\psi=\int_{\mathbb R^d}\psi(u)^2\,du\). It is finite because \(\psi\) is bounded and compactly supported, and positive because \(\psi\) is nonzero and continuous. A change of variables gives the exact squared separation

How Difficult Is the Corresponding Test?

For probability distributions \(P\) and \(Q\), their total variation distance is \(\operatorname{TV}(P,Q)=\sup_A|P(A)-Q(A)|\). A standard testing inequality says that any test between \(P\) and \(Q\) has sum of its two error probabilities at least \(1-\operatorname{TV}(P,Q)\). We will use this fact together with Pinsker’s inequality, \(\operatorname{TV}(P,Q)\leq\sqrt{\operatorname{KL}(P,Q)/2}\), where \(\operatorname{KL}(P,Q)\) denotes Kullback–Leibler divergence.

For the regression distributions, the divergence can be calculated directly. Conditional on the design points, the responses are independent Gaussians with common variance \(\sigma^2\). The KL divergence between two univariate normal distributions with equal variance \(\sigma^2\) and means \(\mu_0,\mu_1\) is \((\mu_1-\mu_0)^2/(2\sigma^2)\). Adding the conditional divergences and then averaging over the common design distribution gives

The first equality uses the independence of the \(n\) observations and the uniform design density. The second uses the definition of \(\Delta^2\). Thus the same integral controls both separation and testing difficulty; the factor \(n\) in the divergence expresses how information accumulates with sample size.

From Testing Error to Estimation Risk

Proof. Define a test \(\phi\) that selects whichever of \(f_0\) and \(f_1\) is closer to \(\hat f\) in \(L_2\), breaking ties in favor of \(f_0\). If \(\phi=1\) under \(f_0\), then \(\|\hat f-f_1\|_2\leq\|\hat f-f_0\|_2\). By the triangle inequality, \(\Delta\leq\|\hat f-f_0\|_2+\|\hat f-f_1\|_2\leq2\|\hat f-f_0\|_2\). Thus on this error event, \(\|\hat f-f_0\|_2^2\geq\Delta^2/4\). Similarly, when \(\phi=0\) under \(f_1\), the squared error relative to \(f_1\) is at least \(\Delta^2/4\). Consequently, \[ E_{f_0}\|\hat f-f_0\|_2^2+E_{f_1}\|\hat f-f_1\|_2^2 \geq\frac{\Delta^2}{4}\{P_{f_0}(\phi=1)+P_{f_1}(\phi=0)\}. \] The sum of testing errors is at least \(1-\operatorname{TV}(P_{f_0},P_{f_1})\). The maximum of two nonnegative risks is at least half their sum, proving the claimed factor \(1/8\). \(\square\)

This result applies to every estimator, not just an estimator that explicitly performs hypothesis testing. The nearest-function test is a device for showing that an estimator with small error under both hypotheses would also yield a highly accurate test.

Choosing the Width and Interpreting the Bound

For the localized Hölder perturbation, the divergence equals \(n a^2h^{2\beta+d}I_\psi/(2\sigma^2)\). Choose \(h=c n^{-1/(2\beta+d)}\), where \(c>0\) is fixed and small enough that \(a^2c^{2\beta+d}I_\psi/(2\sigma^2)\leq1/8\). For all sufficiently large \(n\), this choice also satisfies \(h\leq1/2\), as required for the bump to fit inside the domain. The divergence is then at most \(1/8\), so the theorem and Pinsker’s inequality give a fixed positive multiple of \(\Delta^2\) as a risk lower bound. But

Thus this single-bump construction gives a lower bound of order \(n^{-1}\), with a positive constant independent of \(n\). It does not establish the sharp integrated-risk order \(n^{-2\beta/(2\beta+d)}\) in general. The distinction is visible in \(d=2,\beta=1\): the sharp-rate expression is \(n^{-1/2}\), whereas this two-point calculation gives \(n^{-1}\), a weaker lower bound. Since \(n^{-1}\) is smaller than \(n^{-1/2}\) for large \(n\), the former cannot imply the latter. Establishing the sharper rate requires a stronger construction, such as simultaneous perturbations on multiple regions; that is a different testing argument.

Common Pitfall

A frequent error is to observe that the bump height is of order \(h^\beta\), combine it with a support volume of order \(h^d\), and then claim the separation is \(n^{-2\beta/(2\beta+d)}\) after setting \(h\) proportional to \(n^{-1/(2\beta+d)}\). The correct multiplication is \((h^\beta)^2h^d=h^{2\beta+d}\). Substituting the chosen width gives \((n^{-1/(2\beta+d)})^{2\beta+d}=n^{-1}\), not \(n^{-2\beta/(2\beta+d)}\). Always substitute the bandwidth into the complete separation expression before naming the resulting rate.

A second caution is that smoothness must match the class definition. A triangular bump is Lipschitz but has corners, so it is not a \(C^1\) perturbation under a convention requiring bounded first derivatives. The \(C^\infty\) compactly supported bump used here avoids that issue and can be scaled to lie in the stated Hölder ball.