The Hölder L2 Minimax Upper Rate

From Smoothness to an Upper Risk Bound

In nonparametric regression, a flexible estimator can represent complex functions, but estimating too many coefficients from a finite sample creates noise. A useful upper bound comes from choosing a finite-dimensional space that is rich enough to approximate a smooth regression function, yet small enough that its coefficients can be estimated accurately. The resolution of the space determines both errors.

We derive this trade-off for integrated squared-error risk over an isotropic Hölder ball. The result is an upper bound: it shows that one estimator achieves the stated rate uniformly over the class. By itself, it does not prove that no estimator can do better; that would require a lower-bound argument.

Model, Class, and Risk

Let \(X_i\) be independent and uniformly distributed on \([0,1]^d\), and suppose the observations follow the random-design regression model

Assume \(E[\varepsilon_i\mid X_i]=0\) and \(E[\varepsilon_i^2\mid X_i]\leq \sigma^2\) almost surely. The pairs \((X_i,Y_i)\) are independent and identically distributed. We measure the estimator’s performance by its expected integrated squared error, with integration against the uniform design distribution.

In particular, \(|f(x)|\leq L\). The smoothness condition also gives local polynomial approximations: on a cube of side length \(h\), a degree-\(r\) Taylor polynomial approximates \(f\) with pointwise error at most a constant times \(Lh^\beta\). We give the needed argument below.

The Approximation Space

Divide \([0,1]^d\) into \(m^d\) cubes of side \(h=1/m\). On each cube, use polynomials of total degree at most \(r\), with no continuity constraint between cubes. Let \(S_m\) be the resulting piecewise-polynomial space, and let \(\Pi_m f\) be the orthogonal projection of \(f\) onto \(S_m\) in \(L_2([0,1]^d)\). The dimension of this space is

Here \(M\) is the fixed number of polynomial terms on each cube, depending only on \(d\) and \(\beta\). Thus the total dimension grows proportionally to the number of cubes.

To verify the bound, take one cube \(Q\), choose a corner \(a\), and let \(T_{a,r}\) be the Taylor polynomial of degree \(r\) at \(a\). When \(r=0\), the Hölder condition directly gives \(|f(x)-f(a)|\leq L\|x-a\|^\beta\). When \(r\geq1\), apply the one-dimensional Taylor formula to \(g(t)=f(a+t(x-a))\), \(0\leq t\leq1\). The order-\(r\) derivative of \(g\) is a sum of order-\(r\) partial derivatives of \(f\), multiplied by products of coordinates of \(x-a\). Their \(\alpha\)-Hölder condition bounds the difference between \(g^{(r)}(t)\) and \(g^{(r)}(0)\) by a constant times \(L\|x-a\|^{r+\alpha}t^\alpha\). The integral remainder after the degree-\(r\) Taylor polynomial is therefore at most \(C L\|x-a\|^{r+\alpha}=C L\|x-a\|^\beta\). Since \(x,a\in Q\), \(\|x-a\|\leq\sqrt d\,h\), so the pointwise error on every cube is at most \(C Lh^\beta\). Squaring and integrating over a domain of volume one gives \(\|f-T\|_2^2\leq C L^2h^{2\beta}\) for the piecewise Taylor polynomial \(T\in S_m\). Orthogonal projection has no larger \(L_2\) error than any element of \(S_m\), proving the bound. \(\square\)

Estimating the Polynomial Coefficients

Choose an orthonormal basis \(\phi_1,\ldots,\phi_{K_m}\) for \(S_m\) in \(L_2([0,1]^d)\). Because the basis functions are supported on individual cubes and the polynomial degree is fixed, it can be chosen so that

where \(C_2\) depends only on \(d\) and \(\beta\). Indeed, on a reference unit cube the sum of squares of a fixed finite orthonormal polynomial basis is bounded; rescaling to cubes of side \(1/m\) multiplies the squared basis functions by \(m^d\).

Write the projection as \(\Pi_m f=\sum_{j=1}^{K_m}\theta_j\phi_j\), where \(\theta_j=E[f(X)\phi_j(X)]\). Estimate each coefficient by its sample average:

Uniform design and the conditional mean-zero noise assumption imply \(E[\hat\theta_j]=\theta_j\). This estimator does not require dividing by the number of observations in a cube.

For the proof, orthonormality gives \(\|\hat f_m-\Pi_mf\|_2^2=\sum_{j=1}^{K_m}(\hat\theta_j-\theta_j)^2\). Each coefficient is unbiased, and independence of the observations gives

The conditional mean-zero assumption yields \(E[Y^2\mid X]=f(X)^2+E[\varepsilon^2\mid X]\leq L^2+\sigma^2\). Hence \(E[Y^2]\leq L^2+\sigma^2\), proving the claimed bound with \(C_3=C_2(L^2+\sigma^2)\). \(\square\)

Balancing the Two Errors

The approximation and estimation errors combine exactly in expectation. Since \(f-\Pi_mf\) is orthogonal to \(S_m\) and \(\hat f_m-\Pi_mf\in S_m\), their inner product is zero for every realized estimator. Taking expectations gives

The first term decreases as the partition gets finer; the second increases because the space has more coefficients to estimate. The next theorem turns this bound into a rate.

To prove the theorem, set \(m=\lceil n^{1/(2\beta+d)}\rceil\) and use \(\hat f_m\). Since \(n^{1/(2\beta+d)}\geq1\), this choice satisfies

Consequently,

and

Substituting both inequalities into the risk bound proves the theorem with \(C=C_1+2^dC_3\). \(\square\)

Worked Examples

Common Pitfall and Interpretation

A frequent error is to set the approximation term equal to the estimation term but then report the rate of the resolution \(m\), rather than the rate of the risk. Balancing \(m^{-2\beta}\) with \(m^d/n\) gives \(m\) of order \(n^{1/(2\beta+d)}\); substituting that resolution into either error term gives the risk rate \(n^{-2\beta/(2\beta+d)}\). The exponent for resolution is not the exponent for squared-error risk.

The result is useful because it makes the roles of smoothness, dimension, and sample size explicit. Greater smoothness reduces the approximation error more quickly, while a larger input dimension increases the number of coefficients at a given resolution. The theorem establishes a uniform upper bound for this model and class; it does not, on its own, establish a matching minimax lower bound.