Sobolev Minimax Rates

Setting and Target Risk

A smooth regression function can be estimated by averaging information across nearby inputs, but the attainable accuracy depends on how smooth the function is and how many inputs must be covered. For Sobolev smoothness \(s\) in dimension \(d\), the central balance is between approximation error and the uncertainty from estimating many coefficients. We derive that balance for one explicit model, then show that a matching lower bound rules out a faster rate over the same function class.

Work on the \(d\)-dimensional torus \(\mathbb T^d=[0,1]^d\) with opposite faces identified. This periodic domain gives a Fourier representation without boundary terms. The observations \((X_i,Y_i)\), \(i=1,\ldots,n\), are independent and identically distributed according to \(X_i\sim\operatorname{Unif}(\mathbb T^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 fixed \(\sigma>0\).

The norm in the risk is with respect to Lebesgue measure on the torus. Since the design is uniform, it is also the expected prediction error at an independent input, conditional on the fitted function. Here \(s,d,R,\sigma\) are fixed as \(n\) grows. The result below is a rate statement: its multiplicative constants may depend on these fixed quantities.

Upper Bound by Fourier Truncation

Let \(\{\phi_j\}\) be a real orthonormal Fourier basis, consisting of the constant function and the normalized sine and cosine functions. Retain the basis functions whose frequency has Euclidean length at most an integer \(K\ge1\); denote this finite set by \(J_K\). Its size is at most \(C_dK^d\), for a constant depending only on \(d\). For each retained basis function estimate its coefficient by the empirical average \(n^{-1}\sum_{i=1}^nY_i\phi_j(X_i)\), and set all other coefficients to zero.

The coefficient estimate is unbiased because \(X_i\) is uniform and the basis is orthonormal: \(E_f[Y_i\phi_j(X_i)]=\int_{\mathbb T^d}f(x)\phi_j(x)\,dx\). Also, each real Fourier basis function is bounded in absolute value by \(\sqrt{2}\). Consequently, \(E_f[Y_i^2\phi_j(X_i)^2]\le 2E_f[Y_i^2]\le2(R^2+\sigma^2)\). Independence across observations then gives \(\operatorname{Var}_f(\hat\theta_j)\le2(R^2+\sigma^2)/n\).

Proof. Decompose \(f\) into its projection onto the retained basis functions and its orthogonal remainder. Because the retained and omitted components are orthogonal, the squared error is the sum of the squared coefficient errors on \(J_K\) and the squared norm of the omitted component. Taking expectations, the first term is bounded by \(|J_K|\,2(R^2+\sigma^2)/n\le C K^d/n\). For every omitted frequency, \(\lVert k\rVert>K\), so \((1+4\pi^2\lVert k\rVert^2)^{-s}\le C_s K^{-2s}\). The Sobolev constraint therefore bounds the squared omitted norm by \(C_sR^2K^{-2s}\). Adding these bounds proves the claim. \(\square\)

The first term counts how many coefficients are estimated; the second is the Fourier tail that truncation leaves behind. Choose \(K\) of order \(n^{1/(2s+d)}\). Then \(K^d/n\) and \(K^{-2s}\) are both of order \(n^{-2s/(2s+d)}\).

Lower Bound by a Fourier Hypercube

An upper bound alone does not establish the minimax rate: a different estimator might do better. For a lower bound, construct many functions in the Sobolev ball that are separated in \(L^2\), while making neighboring functions difficult to distinguish from the data. The construction uses only real cosine functions.

Proof. Let \(K\) be a positive integer and use the \(M=K^d\) distinct frequencies with coordinates in \(\{K,K+1,\ldots,2K-1\}\). For each such frequency \(k\), put \(\psi_k(x)=\sqrt{2}\cos(2\pi k\cdot x)\). These functions are orthonormal in \(L^2(\mathbb T^d)\). For a sign vector \(\omega\in\{-1,1\}^M\), define \(f_\omega=\delta\sum_k\omega_k\psi_k\), where \(\delta=aK^{-s-d/2}\) and \(a>0\) will be chosen small.

Each selected frequency has squared length at most \(4dK^2\). The Sobolev norm of the cosine expansion is therefore bounded as follows: \(\lVert f_\omega\rVert_{H^s}^2\le M\delta^2(1+16\pi^2dK^2)^s\le C_{d,s}a^2\) for \(K\ge1\). Choose \(a\) small enough that \(C_{d,s}a^2\le R^2\); every \(f_\omega\) then belongs to the ball.

If \(\omega\) and \(\omega'\) differ in exactly one sign, their regression functions differ by \(2\delta\psi_k\). Let \(P_\omega\) denote the joint distribution of all observed pairs under \(f_\omega\). Conditional on the inputs, the responses are independent Gaussians with common variance \(\sigma^2\). The Gaussian relative entropy formula, followed by averaging over the common uniform design, gives \(\operatorname{KL}(P_\omega,P_{\omega'})=\frac{n}{2\sigma^2}\lVert f_\omega-f_{\omega'}\rVert_2^2=\frac{2n\delta^2}{\sigma^2}\).

Set \(K=\lceil n^{1/(2s+d)}\rceil\). Then \(nK^{-2s-d}\le1\), so the neighboring relative entropy is at most \(2a^2/\sigma^2\). Reduce \(a\), if necessary, so that this is at most \(1/2\). Pinsker's inequality gives total variation distance at most \(\sqrt{\operatorname{KL}/2}\le1/2\) for every neighboring pair.

To turn this into a risk bound, take any estimator with finite \(L^2\) risk and classify its estimated coefficient on each \(\psi_k\) by whether it is nonnegative or negative. If this classification is wrong when the true coefficient is \(\delta\) or \(-\delta\), the squared coefficient error is at least \(\delta^2\). For each pair of vertices differing only in sign \(k\), the average probability of a wrong binary decision is at least \((1-\operatorname{TV})/2\ge1/4\), by the elementary testing bound that the sum of the two error probabilities is at least one minus total variation. Averaging uniformly over all vertices and summing over the \(M\) orthogonal coefficients gives \(\sup_\omega E_\omega\lVert\hat f-f_\omega\rVert_2^2\ge M\delta^2/4=a^2K^{-2s}/4\). Finally, for \(n\ge1\), \(K\le2n^{1/(2s+d)}\), so \(K^{-2s}\ge2^{-2s}n^{-2s/(2s+d)}\). This lower bound applies to every estimator and proves the theorem. \(\square\)

Matching Rate and Its Interpretation

Combining the two bounds gives, for sufficiently large \(n\), \(\mathcal R_n(\mathcal W^s(R))\asymp n^{-2s/(2s+d)}\), where the comparison constants may depend on the fixed model parameters. The exponent reflects a balance: at resolution \(K\), there are order \(K^d\) coefficients to estimate, while Sobolev smoothness makes the squared Fourier tail order \(K^{-2s}\). The lower bound confirms that this trade-off is not merely a limitation of the particular Fourier estimator.

The assumptions are part of the result. The theorem uses a periodic domain, uniform random design, integrated \(L^2\) loss, and independent Gaussian noise with fixed positive variance. It is not, without further argument, a statement for boundary-sensitive domains, nonuniform designs, pointwise loss, or other noise distributions. Those changes can require different conditions or rates.

Common Pitfall

• Using \(s/(2s+d)\) as the squared-error exponent. That exponent omits the conversion from an error amplitude to squared error. Here the Sobolev approximation error is \(K^{-2s}\), and balancing it with \(K^d/n\) yields \(n^{-2s/(2s+d)}\). The corresponding root mean squared error has exponent \(s/(2s+d)\).
• Changing the resolution without changing the bias calculation. Keeping more coefficients reduces the Fourier tail but increases the variance contribution. The chosen \(K\) must balance both terms; choosing it from only one term does not establish the stated rate.