Minimax Integrated Squared-Error Rates

Why a Minimax Rate Is a Two-Sided Claim

A risk calculation for one estimator answers how well that procedure can perform. A minimax rate answers a stronger question: how quickly can the best possible procedure perform in the hardest case within a specified class? For density estimation under integrated squared error, the rate reflects a balance between the difficulty of approximating a smooth density and the information available in a sample of size \(n\).

We study densities on the unit cube \(\Omega=[0,1]^d\), where \(d\) is fixed. The central conclusion is that, for a suitable Hölder class of smoothness \(\beta\), the minimax risk is of order \(n^{-2\beta/(2\beta+d)}\). Establishing this claim requires two different arguments: an estimator whose risk is at most a constant times this rate, and a lower bound showing that no density estimator can do uniformly better.

Risk and the Density Class

For definiteness, take \(\beta>0\), let \(m=\lceil\beta\rceil-1\), and let \(\alpha=\beta-m\), so \(0<\alpha\leq 1\). The isotropic Hölder condition used here requires derivatives through order \(m\) to be bounded, with derivatives of order \(m\) satisfying an \(\alpha\)-Hölder condition. When \(m=0\), this means \(f\) itself is \(\alpha\)-Hölder. At integer \(\beta\), this convention requires derivatives through order \(\beta-1\) to be Lipschitz.

Let \(\mathcal H(\beta,L,c_0,c_1)\) be the densities on \(\Omega\) satisfying this Hölder condition with norm at most \(L\), and \(c_0\leq f(x)\leq c_1\) almost everywhere. Assume \(c_0<1<c_1\), \(L\) is large enough that the uniform density \(f_0(x)=1\) lies strictly inside the smoothness constraint, and the class has room for small smooth perturbations of \(f_0\). These interior conditions matter for the lower bound: the alternatives must remain densities in the class.

Worked Examples: Reading the Rate

An Upper Bound from Piecewise-Polynomial Projection

Divide the cube into \(J^d\) subcubes of side length \(h=1/J\). On each subcube, use polynomials of total degree at most \(m\), and let \(V_h\) be the resulting finite-dimensional subspace of \(L^2(\Omega)\). Its dimension \(K_h\) is at most \(C h^{-d}\), where constants in this tutorial may depend on \(d,\beta,L,c_1\), but not on \(n\) or \(h\). Choose an orthonormal basis \(\phi_1,\ldots,\phi_{K_h}\) of \(V_h\) and define the empirical projection $$ \tilde f_h(x)=\sum_{k=1}^{K_h}\left\{\frac{1}{n}\sum_{i=1}^n\phi_k(X_i)\right\}\phi_k(x). $$ This estimate integrates to one because the constant function belongs to \(V_h\), but it need not be nonnegative. We will correct that issue after bounding its error.

To establish the bound, first consider \(\tilde f_h\). Its expectation is the \(L^2\) projection \(\Pi_h f\). On each subcube, Taylor approximation by a polynomial of degree \(m\), with the Hölder condition on the derivatives of order \(m\), gives a pointwise approximation error bounded by \(C h^\beta\). Since the cube has volume one, this yields $$ \|f-\Pi_h f\|_2^2\leq C h^{2\beta}. $$ The Taylor remainder statement also covers \(m=0\), where it follows directly from the Hölder condition on \(f\).

The random coefficient of \(\phi_k\) has variance \(n^{-1}\operatorname{Var}_f(\phi_k(X))\). Orthonormality and the bound \(f\leq c_1\) therefore give $$ E_f[\|\tilde f_h-\Pi_h f\|_2^2] =\frac{1}{n}\sum_{k=1}^{K_h}\operatorname{Var}_f(\phi_k(X)) \leq \frac{1}{n}\int_\Omega f(x)\sum_{k=1}^{K_h}\phi_k(x)^2\,dx \leq \frac{c_1 K_h}{n} \leq C\frac{h^{-d}}{n}. $$ The squared-error decomposition into projection bias and centered coefficient variance has no cross term: \(E_f[\tilde f_h-\Pi_h f]=0\). Adding the two bounds gives the displayed risk bound for \(\tilde f_h\), viewed for now as an \(L^2\)-valued estimate.

To obtain an admissible density estimator, let \(\mathcal C=\{g\in L^2(\Omega):g\geq0\text{ almost everywhere},\ \int_\Omega g=1\}\), and set \(\hat f_h=P_{\mathcal C}\tilde f_h\), the \(L^2\) metric projection. The set \(\mathcal C\) is nonempty, closed, and convex: nonnegativity is a closed convex constraint in \(L^2\), and integration is a continuous linear functional on \(L^2(\Omega)\) because \(\Omega\) has finite volume. Thus the projection exists and is unique. Since the projection is continuous, this defines a measurable estimator.

For any \(z\in L^2\), write \(p=P_{\mathcal C}z\). The metric projection property gives \(\langle z-p,f-p\rangle\leq0\) for every \(f\in\mathcal C\). Expanding the square, $$ \|z-f\|_2^2=\|z-p\|_2^2+\|p-f\|_2^2+2\langle z-p,p-f\rangle \geq \|p-f\|_2^2. $$ Every \(f\in\mathcal H\) belongs to \(\mathcal C\). Consequently, projecting cannot increase its squared error relative to \(f\). The risk bound for \(\tilde f_h\) therefore holds for the density estimator \(\hat f_h\) as well. \(\square\)

A Matching Lower Bound Using Density Alternatives

An upper bound alone does not show that its rate is optimal. For a lower bound, construct many densities that are close enough to be hard to distinguish from data, but far enough apart in integrated squared error. Choose a nonzero smooth function \(\psi\), supported strictly inside the unit cube, with \(\int\psi=0\). Partition \(\Omega\) into \(M=J^d\) cubes of side \(h=1/J\). For cube \(j\), with lower corner \(a_j\), define \(\psi_j(x)=\psi((x-a_j)/h)\), taking it to be zero outside that cube. For sign vectors \(\theta\in\{-1,1\}^M\), set $$ f_\theta(x)=1+\delta h^\beta\sum_{j=1}^{M}\theta_j\psi_j(x). $$ Each perturbation has integral zero. Since the supports are disjoint and \(h\leq1\), choosing \(\delta>0\) sufficiently small ensures \(f_\theta\geq1/2\). Scaling the derivatives and Hölder seminorms shows that the perturbations have uniformly bounded Hölder norm; choosing \(\delta\) small enough puts every \(f_\theta\) in the specified class.

Here is the testing argument. Two sign vectors differing only in coordinate \(j\) give densities whose difference is \(2\delta h^\beta\psi_j\). For densities \(p,q\) with \(q\geq1/2\), the inequality \(\operatorname{KL}(p,q)\leq\int (p-q)^2/q\) implies $$ \operatorname{KL}(f_\theta,f_{\theta'}) \leq 8\delta^2 h^{2\beta}\int_\Omega\psi_j(x)^2\,dx =8\delta^2\|\psi\|_2^2 h^{2\beta+d}. $$ The last equality follows by the change of variables \(u=(x-a_j)/h\). For \(n\) independent observations, the Kullback–Leibler divergence is \(n\) times the one-observation divergence. Take \(J=\lceil A n^{1/(2\beta+d)}\rceil\), so \(h=1/J\) is comparable to \(n^{-1/(2\beta+d)}\). A sufficiently large fixed \(A\) makes the divergence between neighboring \(n\)-sample distributions small enough that their total variation distance is at most \(1/2\), by Pinsker’s inequality \(\operatorname{TV}(P,Q)\leq\sqrt{\operatorname{KL}(P,Q)/2}\).

To translate this indistinguishability into squared-error risk, the functions \(q_j=\psi_j/\|\psi_j\|_2\) are orthonormal because their supports are disjoint. The coefficient of \(f_\theta-1\) along \(q_j\) is \(\theta_j B\), where \(B=\delta h^\beta\|\psi_j\|_2=\delta\|\psi\|_2h^{\beta+d/2}\). Given any estimator, classify the sign \(\theta_j\) by the sign of \(\langle\hat f-1,q_j\rangle\). Whenever this sign is wrong, the squared error in that coefficient is at least \(B^2\). Pairing sign vectors that differ only in bit \(j\), the average probability of misclassifying that bit is at least \((1-\operatorname{TV})/2\geq1/4\). Bessel’s inequality says the total squared error is at least the sum of squared errors in these orthonormal coefficients. Averaging over all sign vectors therefore gives $$ \sup_{\theta}E_\theta[\|\hat f-f_\theta\|_2^2] \geq \frac{1}{4}M B^2 =\frac{\delta^2\|\psi\|_2^2}{4}h^{2\beta}. $$ Since \(h\) is comparable to \(n^{-1/(2\beta+d)}\), this is at least a constant times \(n^{-2\beta/(2\beta+d)}\). The inequality holds for every estimator, so it also holds for the infimum defining the minimax risk. \(\square\)

Conclusion and Common Pitfall

Combining the estimator upper bound at \(h\) of order \(n^{-1/(2\beta+d)}\) with the density-specific lower bound gives $$ R_n(\mathcal H)\asymp n^{-2\beta/(2\beta+d)}. $$ The notation \(\asymp\) means bounded above and below by positive constant multiples for sufficiently large \(n\). Smoothness improves the rate, while dimension slows it.

Common pitfall: A linear projection estimate can have a negative value, so it is not necessarily a density. Its risk bound by itself does not establish an upper bound when the minimax infimum is over density estimators. The correction is to project the estimate onto the closed convex set of nonnegative functions integrating to one. Because the true density belongs to that set, the projection inequality proves that this correction cannot increase integrated squared error. On the lower-bound side, arbitrary signed perturbations are also insufficient: the alternatives must integrate to one, stay nonnegative, and satisfy the smoothness constraints.