Projection Estimators and Linear Minimax Risk
Projection estimators retain finitely many coefficients in an orthogonal expansion. Omitted coefficients contribute approximation bias, while estimating retained coefficients contributes variance. We derive this risk decomposition, explain what a data-based tuning criterion does and does not guarantee, and solve the weighted Gaussian problem over an ellipsoid.
Let \((\varphi_j)_{j\ge1}\) be an orthonormal basis of \(L^2[0,1]\), and \(\theta_j=\int_0^1f\varphi_j\). Every \(f\in L^2\) has \(f=\sum_j\theta_j\varphi_j\) in \(L^2\); uniform convergence requires additional regularity and is not needed for Parseval risk calculations.
For fixed-design regression \(Y_i=f(X_i)+\xi_i\), with independent centered errors, a coefficient estimate and its series estimator are
For arbitrary deterministic designs, \(\mathbb E\widehat\theta_j=n^{-1}\sum_if(X_i)\varphi_j(X_i)\) need not equal the integral \(\theta_j\). If this quadrature bias is \(b_{j,n}\), then orthogonality gives
There are no integrated cross terms, even if the coefficient estimates are correlated. A continuous representative of \(f\), or otherwise specified point values, is needed to define fixed-design regression on an \(L^2\) class.
For iid observations from a density \(p\) on \([0,1]\), instead define \(c_j=\int p\varphi_j\), \(\widehat c_j=n^{-1}\sum_i\varphi_j(X_i)\), and \(\widehat p_{nN}=\sum_{j=1}^N\widehat c_j\varphi_j\). The truncation index is \(N\), not the sample size \(n\).
For integer \(\beta\ge1\), the periodic Sobolev class has \(f^{(\beta-1)}\) absolutely continuous, \(\int_0^1|f^{(\beta)}|^2\le L^2\), and matching endpoint derivatives \(f^{(j)}(0)=f^{(j)}(1)\), \(0\le j<\beta\). Use \(\varphi_1=1\), \(\varphi_{2m}=\sqrt2\cos(2\pi mx)\), \(\varphi_{2m+1}=\sqrt2\sin(2\pi mx)\). Integration by parts cancels the periodic boundary terms; differentiation rotates each sine/cosine pair and multiplies it by \(2\pi m\). Parseval therefore gives
With \(Q=L^2/\pi^{2\beta}\), let \(\Theta(\beta,Q)=\{\theta\in\ell^2:\sum_ja_j^2\theta_j^2\le Q\}\) and \(\widetilde W(\beta,L)=\{f\in L^2:\theta\in\Theta(\beta,Q)\}\). The ellipsoid definition also makes sense for every real \(\beta>0\), without requiring classical integer derivatives.
An oracle truncation \(N_n^*(f)\) minimizes the true expected risk over a specified candidate set, if the minimum is attained. Because it depends on unknown \(f\), it is generally unavailable. More generally, for procedures \(\widehat\theta_\tau\) and loss \(\mathcal L\), the oracle minimizes \(R_\theta(\tau)=\mathbb E_\theta\mathcal L(\widehat\theta_\tau,\theta)\). Loss is a function of an estimate and parameter; risk is its expectation. Both the candidate class and the loss determine this benchmark.
Remark 1. For density estimation assume \(p\in L^2[0,1]\) and \(A_j=\int\varphi_j^2p<\infty\) for the retained indices; the latter is automatic for the trigonometric basis. Then \(\mathbb E\widehat c_j=c_j\) and \(\operatorname{Var}(\widehat c_j)=(A_j-c_j^2)/n\). Parseval, first for each realized coefficient vector and then in expectation, yields
For \(n\ge2\), define
Since \(\mathbb E\widehat c_j^2=A_j/n+(n-1)c_j^2/n\), each summand has expectation
Consequently \(\mathbb E\widehat J(N)=\operatorname{MISE}(N)-\|p\|_2^2\). Minimizing \(\widehat J\) over a finite candidate set, with deterministic tie-breaking, defines a measurable data-based selector. Equality of the expected criteria does not imply that this random selector minimizes true risk, and a minimum over all integers need not exist without further control. Any oracle inequality for the selected estimate requires a separate argument.
For the trigonometric basis, \(A_1=1\), \(A_{2m}=1+c_{4m}/\sqrt2\), and \(A_{2m+1}=1-c_{4m}/\sqrt2\), by the double-angle identities. Thus \(\sum_{j=1}^NA_j=N\) for odd \(N\); for even \(N\) it equals \(N+c_{2N}/\sqrt2\). Since \(|c_{2N}|\le\sqrt2\int p=\sqrt2\), both cases give
for a density in the Sobolev ellipsoid, because \(a_{N+1}\ge N^\beta\). Choosing \(N\) of order \(n^{1/(2\beta+1)}\) proves the rate \(n^{-2\beta/(2\beta+1)}\).
Remark 2. Here is the complete density lower-bound construction underlying the corresponding rate. Let \(\mathcal P(\beta,L)\) be the Hölder densities on \(\mathbb R\) with degree \(\ell=\lceil\beta\rceil-1\) and seminorm bound \(L\). There is a constant \(c>0\) such that
Choose a sufficiently spread-out Gaussian density \(p_0\) whose Hölder seminorm is at most \(L/2\), and put \(b_0=\inf_{[0,1]}p_0>0\). Choose a fixed smooth nonzero \(g\), supported inside \((0,1)\), with \(\int g=0\); the derivative of a smooth compactly supported bump provides one. Let \(h=1/m\) and \(g_k(x)=a h^\beta g((x-(k-1)h)/h)\), \(1\le k\le m\), for a sufficiently small constant \(a>0\). Define
Each perturbation integrates to zero, so \(p_\omega\) integrates to one. The supports are disjoint and the pointwise perturbation is at most \(a h^\beta\|g\|_\infty\), which is below \(b_0/2\) for large \(m\); hence these are nonnegative densities. Scaling gives a Hölder seminorm bounded by \(C_ga\) for a bump. Across two different supports, compare each derivative value with its zero value at the intervening endpoint; the sum of the two powers is at most \(2|x-y|^{\beta-\ell}\). Thus the bound remains \(2C_ga\), independently of \(m\). Choose \(a\) so it is at most \(L/2\). This verifies membership of every perturbation in the stated class.
The Varshamov–Gilbert lemma supplies \(M+1\) binary vectors, including zero, with pairwise Hamming distances at least \(m/8\) and \(\log(M+1)\ge c_0m\), for all sufficiently large \(m\). Disjoint supports give the squared distance
Write \(v=p_\omega-p_0\). Using \(\log(1+v/p_0)\le v/p_0\) and \(\int v=0\),
For \(n\) iid observations the divergence is multiplied by \(n\), as follows by summing the log likelihood over observations. Choose \(m=\lceil A n^{1/(2\beta+1)}\rceil\), with \(A\) sufficiently large; then \(nCh^{2\beta}/\log(M+1)\le C'n h^{2\beta+1}\) is at most \(1/4\). The entropy testing bound proved in the preceding local-polynomial note gives average classification error at least \(1/2\) for large \(n\). Selecting the nearest density to any proposed estimator converts squared \(L^2\) error smaller than one quarter of the squared separation into correct classification. Its maximum risk is therefore at least a positive constant times \(h^{2\beta}\), proving the claim. The packing lemma supplies separated alternatives; the divergence and testing steps, not the packing lemma alone, turn them into a minimax bound.
1. Adaptation, and Asymptotic Efficiency
For a squared semimetric loss let \(r(\widehat\theta_n)=\sup_{\theta\in\Theta}\mathbb E_\theta d^2(\widehat\theta_n,\theta)\) and \(\mathcal R_n^*=\inf_{\widehat\theta_n}r(\widehat\theta_n)\). A rate \(\psi_n\) is minimax optimal if \(0<c\le\liminf\psi_n^{-2}\mathcal R_n^*\le\limsup\psi_n^{-2}\mathcal R_n^*\le C<\infty\). An estimator is asymptotically efficient if \(r(\widehat\theta_n)/\mathcal R_n^*\to1\). This is stronger than attaining only the rate. Adaptation asks whether one procedure can retain the desired performance over multiple smoothness classes without knowing which class contains the truth; nothing in the oracle definition itself proves adaptation.
In the white-noise model \(dY=fdt+\varepsilon dW\), define the Pinsker estimator by \(\widehat f_\varepsilon=\sum_j(1-\kappa^*a_j)_+y_j\varphi_j\), where \(y_j=\int\varphi_jdY\) and
Theorem 3. For every \(\beta,L>0\), using the ellipsoid definition of \(\widetilde W\),
where \(C^*=L^{2/(2\beta+1)}(2\beta+1)^{1/(2\beta+1)}[\beta/(\pi(\beta+1))]^{2\beta/(2\beta+1)}\).
The full upper and Gaussian-prior lower bound are proved in the Pinsker theorem note. Its proof uses only the coefficient weights and works for all real positive \(\beta\); the integer restriction there concerns the classical Sobolev interpretation. In particular, the theorem gives a risk ratio tending to one, rather than just matching exponents.
For equally spaced regression \(Y_i=f(i/n)+\xi_i\), \(\xi_i\sim \mathcal{N}(0,\sigma^2)\), the same sharp constant after replacing \(\varepsilon\) by \(\sigma/\sqrt n\) is valid for \(\beta>1/2\), with the continuous periodic representative. This needs a discretization argument; it is not a literal specialization of the white-noise observation.
Here is that argument. Write the complex Fourier coefficients as \(c_k\), \(k\in\mathbb Z\). The ellipsoid bound gives \(\sum_{k\ne0}|k|^{2\beta}|c_k|^2\le C L^2\). For \(\beta>1/2\), Cauchy–Schwarz and \(\sum_{k\ne0}|k|^{-2\beta}<\infty\) give absolute uniform convergence of the Fourier series. The discrete coefficient at frequency \(k\) therefore has mean \(\sum_{r\in\mathbb Z}c_{k+rn}\). For \(|k|\le m<n/4\), its alias error \(d_k=\sum_{r\ne0}c_{k+rn}\) satisfies
The residue classes for distinct \(|k|\le m\) are disjoint. Summing proves \(\sum_{|k|\le m}|d_k|^2\le C L^2n^{-2\beta}\), also in the equivalent real basis. The real discrete trigonometric coefficients below frequency \(m\) have independent noise variance \(\sigma^2/n\), by exact grid orthogonality and Gaussianity.
The Pinsker cutoff has \(m\asymp n^{1/(2\beta+1)}=o(n)\); hence it lies in this range eventually. Its squared alias error is \(O(n^{-2\beta})=o(n^{-2\beta/(2\beta+1)})\). By Cauchy–Schwarz, the cross term between this deterministic error and the ideal estimator error is also negligible relative to the latter's risk: it is bounded by twice the product of their root mean squared errors. This proves the sharp upper bound. For the lower bound restrict to the finite Fourier submodel supported on the same active frequencies. There is no aliasing, and the remaining orthogonal coordinates are independent parameter-free Gaussian noise. The finite Gaussian prior and outside-mass argument in Pinsker's proof therefore apply unchanged. The regression minimax risk is consequently
For \(\beta\le1/2\), this argument fails and an \(L^2\) equivalence class does not itself specify values at the sampled points; the unrestricted discrete-regression assertion requires additional assumptions.
1.1. Reduction to Linear Minimax Estimators
The sequence observations are \(y_j=\theta_j+\varepsilon\xi_j=\int\varphi_jdY\), not the noiseless integrals \(\int\varphi_j f\). For deterministic square-summable weights,
Each coordinate is minimized separately: its derivative is \(2(\lambda_j-1)\theta_j^2+2\varepsilon^2\lambda_j\), giving
The minimizing sequence is in \(\ell^2\), since \(\sum_j(\lambda_j^{\rm oracle})^2\le\varepsilon^{-2}\|\theta\|_2^2\). One summed first-order equation would not determine all the individual weights.
Lemma 4. Suppose \(a_j\ge0\) is nondecreasing and tends to infinity, and \(Q>0\). The auxiliary equation below has a unique solution \(\kappa>0\).
Proof. The left side as a function of \(\kappa\) is continuous, strictly decreasing while positive, tends to infinity at zero, and becomes zero at the reciprocal of the smallest positive \(a_j\). Continuity follows from finite support of the summands on every compact subinterval of \((0,\infty)\). This proves a unique root. The numbers \(S_j=\varepsilon^2\sum_{m\le j}a_m(a_j-a_m)\) increase to infinity. If \(A=\varepsilon^2\sum_{m\le N}a_m\), \(B=\varepsilon^2\sum_{m\le N}a_m^2\), then \(S_N=Aa_N-B<Q\le Aa_{N+1}-B=S_{N+1}\). Thus \(a_N<1/\kappa\le a_{N+1}\) for the claimed formula, so precisely its first \(N\) terms are active; substitution proves (1). ◻
Define \(\ell_j=(1-\kappa a_j)_+\) and \(D^*=\varepsilon^2\sum_j\ell_j\). The factor is \(\varepsilon^2\) throughout.
Lemma 5. For \(\Theta=\{\theta\in\ell^2:\sum_ja_j^2\theta_j^2\le Q\}\), assume finitely many \(a_j=0\), a positive solution of (1), and \(D^*<\infty\). Then
Proof. The general minimax inequality places \(\sup_\theta\inf_\lambda R\) below \(\inf_\lambda\sup_\theta R\), which is no larger than \(\sup_\theta R(\ell,\theta)\). It suffices to bound the two ends.
For the upper bound, zero-weight coordinates have \(\ell_j=1\) and no bias. On other coordinates \((1-\ell_j)/a_j\le\kappa\), so
We used (1) and \(\ell_j+\kappa a_j=1\) on active coordinates. The weights are admissible since \(\sum_j\ell_j^2\le\sum_j\ell_j<\infty\).
For the lower bound put \(v_j^2=\varepsilon^2\ell_j/(\kappa a_j)\) on any finite set of positive-weight coordinates, zero on the other positive-weight coordinates, and \(v_j=M\) on zero-weight coordinates. Equation (1) gives \(\sum_ja_j^2v_j^2\le Q\), and the vector lies in \(\ell^2\). Its oracle risk is
Let the finite sets increase to all positive-weight coordinates and \(M\to\infty\). The limit is \(D^*\), giving the reverse bound without assuming that a least-favorable vector exists at the unbounded zero coordinates. ◻
Remark 6. The sequence \(\ell\) is the Pinsker weight and \(\widehat\theta_j=\ell_jy_j\) the Pinsker estimator. Lemma 5 solves the linear problem exactly; the Gaussian-prior lower bound in Theorem 3 is the additional step that establishes asymptotic optimality among all estimators.