Noise Assumptions And Nonparametric Rates

Why the Noise Model Matters

In nonparametric regression, smoothness controls how well a regression function can be approximated, while noise controls how much the data fluctuate around it. Under common conditions, Gaussian, bounded, and sub-Gaussian noise lead to the same exponent for integrated squared-error risk. But this agreement has limits: an upper bound may need only a finite variance, whereas a lower bound needs a noise model whose distributions remain statistically difficult to distinguish when the regression function changes slightly.

We use \(X\in[0,1]^d\) with the uniform distribution and observe independent pairs \((X_i,Y_i)\), where \(Y_i=f(X_i)+\varepsilon_i\). The errors have conditional mean zero. The loss for an estimator \(\hat f\) is the integrated squared-error risk \(E\|\hat f-f\|_2^2\), with \(\|g\|_2^2=\int_{[0,1]^d}g(x)^2\,dx\). Assume \(f\) belongs to a fixed smoothness class with smoothness \(s>0\) and radius bounded by a constant. The class is taken to have the usual partition approximation error of order \(K^{-2s/d}\) in squared \(L_2\) norm when using \(K\) suitably arranged local polynomial pieces.

Rate convention: For such a class, the usual integrated squared-error minimax rate is \(n^{-2s/(2s+d)}\): the minimax risk is bounded above and below by positive constants times this quantity. Constants may depend on the smoothness class, dimension, and noise scale, but not on \(n\).

Three Noise Conditions

The assumptions describe different features of the conditional distribution of \(Y\) given \(X\). A Gaussian error is unbounded but has a precisely controlled distribution. A bounded error has bounded magnitude, while a sub-Gaussian error has tails no heavier than a Gaussian in the moment-generating-function sense.

Definitions: A centered error is conditionally \(\sigma\)-sub-Gaussian if, for every real \(t\), \(E[\exp(t\varepsilon)\mid X]\leq \exp(\sigma^2t^2/2)\) almost surely. It is bounded if \(|\varepsilon|\leq B\) almost surely for some fixed \(B\). Gaussian regression noise means \(\varepsilon\mid X\sim N(0,\sigma^2)\), independent of \(X\).

A bounded, conditionally centered error is sub-Gaussian with a scale controlled by its bound, by Hoeffding’s lemma. Gaussian noise is also sub-Gaussian. These facts are useful for concentration inequalities, but the expected integrated squared-error rate is not generally determined by tail behavior alone. In particular, when conditional variances are uniformly bounded, finite second moments can suffice for an upper bound based on squared-error averages.

The model for bounded noise needs care. Bounded responses, such as Bernoulli outcomes, are one natural model: \(Y\in\{0,1\}\), \(E[Y\mid X=x]=f(x)\), and therefore \(\varepsilon=Y-f(X)\) is bounded by one. This is not the same as assuming an additive error with a fixed distribution supported on a bounded interval and then shifting that distribution by \(f(x)\). The distinction matters for lower bounds.

Worked Example: Reading the Rate in One Dimension

Suppose \(d=1\) and the function has smoothness \(s=1\). The usual squared-error rate has exponent

\frac{2s}{2s+d}=\frac{2}{3}, \qquad R_n\asymp n^{-2/3}.

For \(n=10{,}000\), this rate is \(10{,}000^{-2/3}\). Since \(10{,}000=10^4\), it equals \(10^{-8/3}\), approximately \(0.00215\). The asymptotic statement is about order, not an exact risk: its hidden constant depends on the class and noise scale. Replacing Gaussian noise by bounded noise does not, by itself, change this exponent under the conditions considered here.

Why the Upper-Rate Exponent Persists

The basic bias–variance balance explains why many noise distributions give the same exponent. A partition or local polynomial estimator with \(K\) pieces has squared approximation error of order \(K^{-2s/d}\). If the conditional error variance is at most a constant, the contribution from estimating the local pieces is of order \(K/n\). Thus the characteristic bound is

E\|\hat f-f\|_2^2 \ \lesssim\ K^{-2s/d}+\frac{K}{n}.

Balancing the two terms gives \(K^{1+2s/d}\asymp n\), hence \(K\asymp n^{d/(2s+d)}\). Substitution yields \(n^{-2s/(2s+d)}\). Sub-Gaussian tails are valuable for exponential deviation bounds, and bounded responses can simplify concentration arguments, but neither is needed to perform this exponent calculation. For the expected-risk bound, the essential noise contribution is a bounded conditional second moment, together with conditions ensuring the local design is estimable.

Upper-rate result: Suppose the approximation error is \(O(K^{-2s/d})\), the local estimation variance contributes \(O(K/n)\), and the design and estimator satisfy these bounds uniformly over the smoothness class. Then choosing \(K\asymp n^{d/(2s+d)}\) gives \(E\|\hat f-f\|_2^2=O(n^{-2s/(2s+d)})\). A uniform conditional variance bound is sufficient for the variance calculation; Gaussianity is not required.

The claim is conditional on the stated approximation and design bounds. It is not a claim that arbitrary error distributions, or arbitrary estimators, automatically achieve the rate. For example, a heavy-tailed error may have infinite variance, in which case a squared-error analysis of ordinary local averages need not give a finite bound. Robust estimation can sometimes recover useful rates under weaker tail conditions, but that requires separate assumptions and methods.

Worked Example: Balancing Approximation and Noise

Take \(d=2\) and \(s=1\). With \(K\) local pieces, the two terms in the risk bound are \(K^{-1}\) and \(K/n\). Equating them gives \(K^{-1}=K/n\), so \(K^2=n\) and \(K=n^{1/2}\). The resulting risk order is \(n^{-1/2}\).

At \(n=10{,}000\), this calculation suggests \(K=100\) and each term has order \(0.01\). It does not assert that the total risk equals \(0.02\), because the bound has constants and may contain additional lower-order terms. The same balance applies whether the errors are Gaussian, bounded, or sub-Gaussian, provided the upper-bound conditions hold.

Lower Bounds Depend on Distinguishability

A minimax lower bound shows that no estimator can do uniformly better over the class. The usual smooth bump construction creates many regression functions that differ in small, disjoint regions. To show the data cannot reliably identify which function generated the observations, one controls the Kullback–Leibler divergence between the corresponding data distributions. The needed divergence bound depends on the noise model.

For Gaussian regression with known variance \(\sigma^2\), two regression functions \(f\) and \(g\) satisfy

\operatorname{KL}(P_f^{(n)},P_g^{(n)}) =\frac{n}{2\sigma^2}\|f-g\|_2^2.

Here \(P_f^{(n)}\) denotes the joint law of the \(n\) observations when the regression function is \(f\). Conditional on the design points, the log likelihood ratio for one response has expectation \((f(X)-g(X))^2/(2\sigma^2)\). Averaging over the uniform design gives \(\|f-g\|_2^2/(2\sigma^2)\). Independence makes the \(n\)-observation divergence \(n\) times this quantity, proving the identity.

For a smoothness-\(s\) bump of width \(h\) and height proportional to \(h^s\), its squared \(L_2\) separation from the zero function is proportional to \(h^{2s+d}\). The Gaussian divergence for one such local change is therefore of order \(nh^{2s+d}\). Taking \(h\) of order \(n^{-1/(2s+d)}\) keeps this divergence bounded. There are order \(h^{-d}\) disjoint locations for such bumps; the standard Assouad hypercube argument then gives a risk lower bound of order \(h^{2s}=n^{-2s/(2s+d)}\).

Worked Example: A Bounded-Response Lower-Bound Model

Let \(Y\mid X=x\) be Bernoulli with success probability \(f(x)\), and consider functions taking values in \([1/4,3/4]\). The response is bounded, and \(E[Y\mid X=x]=f(x)\). For Bernoulli probabilities \(p,q\), the divergence is

\operatorname{KL}(\operatorname{Bern}(p),\operatorname{Bern}(q)) =p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}.

Using \(\log u\leq u-1\) on both terms gives

\operatorname{KL}(\operatorname{Bern}(p),\operatorname{Bern}(q)) \leq \frac{(p-q)^2}{q(1-q)}.

For \(q\in[1/4,3/4]\), \(q(1-q)\geq 3/16\), so the divergence is at most \((16/3)(p-q)^2\). For the \(n\) observations, averaging over \(X\) and summing gives \(\operatorname{KL}(P_f^{(n)},P_g^{(n)})\leq (16/3)n\|f-g\|_2^2\). Thus the same smooth bump construction has bounded neighboring divergences when \(h\asymp n^{-1/(2s+d)}\). The Assouad argument yields the same \(n^{-2s/(2s+d)}\) lower-bound order, now in a bounded-response model.

Lower-rate result: If a smoothness class contains the usual disjoint bump hypercube and neighboring data distributions have Kullback–Leibler divergence bounded by a fixed constant at bump width \(h\), with \(h\asymp n^{-1/(2s+d)}\), the Assouad lower bound is of order \(n^{-2s/(2s+d)}\). Gaussian regression satisfies the required divergence control, as does the bounded-response Bernoulli model above when its probabilities stay away from zero and one.

A Pitfall: Bounded Does Not Automatically Mean Lower-Bound Friendly

It is tempting to argue that bounded noise always has the same lower bound as Gaussian noise because both are well behaved. That reasoning is incomplete. A lower bound needs nearby regression functions to produce distributions with controlled divergence, not merely errors of bounded magnitude.

For example, consider additive uniform errors \(\varepsilon\sim\operatorname{Uniform}[-1,1]\), independent of \(X\). If \(f(x)=0\) and \(g(x)=\delta>0\) at a design point, the conditional response supports are \([-1,1]\) and \([\delta-1,\delta+1]\). The second distribution assigns positive probability to \((1,1+\delta]\), where the first assigns probability zero. Consequently, the divergence from the shifted distribution to the unshifted one is infinite. The Gaussian divergence formula cannot be carried over just because the uniform error is bounded.

This observation does not prove that the minimax rate must change for every bounded additive-noise model. It shows that this particular divergence argument does not establish the desired lower bound. One must either choose a different valid comparison or impose a noise model with a suitable divergence property. Bounded-response Bernoulli regression supplies one such model and demonstrates that boundedness itself is compatible with the usual rate.

Key takeaway: For the usual expected integrated squared-error exponent, Gaussianity is often stronger than necessary for an upper bound. A bounded second moment can be enough. A matching lower bound is a separate matter: verify how the observation distributions change when the regression function is perturbed.

Check Your Understanding

Use the assumptions and distinctions developed above to answer these questions.

For smoothness \(s=2\) in dimension \(d=1\), what is the usual integrated squared-error exponent?
Why can bounded conditional variance suffice for an expected-risk upper-rate calculation even when the errors are not Gaussian?
What feature of the Bernoulli model keeps its divergence quadratic in a small change of the regression function?
Why does shifting a uniform error distribution create a difficulty for a Gaussian-style lower-bound argument?
State the balance between approximation and estimation terms that produces the usual rate, and solve for \(K\) in terms of \(n,s,d\).