Minimax Lower Bounds in a Diagonal Kernel Model

Why a Lower Bound Is Needed

An estimator’s risk can be bounded from above by analyzing its bias and variance. But an upper bound alone does not say whether its rate is the best any estimator could achieve. A minimax lower bound addresses that question by showing that, over a specified class of targets, every estimator must incur at least a certain prediction risk.

We study a diagonal Gaussian sequence model. Its coordinates represent prediction-relevant spectral directions, and its ellipsoid of possible signals encodes a source-smoothness restriction. The lower bound comes from constructing many nearby signals that are difficult to distinguish from noisy observations but remain separated in prediction loss.

Diagonal Model and Source Ellipsoid

Let $(\mu_j)_{j\geq 1}$ be a nonincreasing sequence of positive kernel eigenvalues. Write $f_j$ for the coefficient of a target function in the corresponding eigenfunction direction. Prediction error in these coordinates is weighted by the eigenvalues: its squared norm is $\sum_{j\geq 1}\mu_j(\hat f_j-f_j)^2$. Define the prediction coordinate $\theta_j=\sqrt{\mu_j}f_j$. The loss is then the ordinary squared sequence error $\sum_{j\geq 1}(\hat\theta_j-\theta_j)^2$.

We observe one noisy sequence $Y=(Y_j)_{j\geq 1}$, with independent coordinates. The sample size $n$ determines the noise variance in every coordinate. For a source condition $f_j=\mu_j^r g_j$, where $r\geq 0$ and $\sum_j g_j^2\leq R^2$, the prediction coordinates satisfy $\theta_j=\mu_j^{r+1/2}g_j$. The half-power arises from converting function coefficients to prediction coordinates.

Definition: For $s=r+1/2>0$, the diagonal Gaussian sequence model and its source ellipsoid are $$ Y_j=\theta_j+n^{-1/2}\xi_j,\qquad \xi_j\stackrel{\mathrm{ind}}{\sim}N(0,1),\qquad \Theta_s(R)=\left\{\theta:\sum_{j\geq 1}\frac{\theta_j^2}{\mu_j^{2s}}\leq R^2\right\}. $$ An estimator $\hat\theta=(\hat\theta_j)_{j\geq1}$ has prediction risk $E_\theta\|\hat\theta-\theta\|_2^2$, where $\|u\|_2^2=\sum_j u_j^2$. The minimax risk is $$ \mathcal R_n(\Theta_s(R))=\inf_{\hat\theta}\sup_{\theta\in\Theta_s(R)}E_\theta\|\hat\theta-\theta\|_2^2, $$ with the infimum over measurable estimators based on the observed sequence.

The ellipsoid restricts signals more strongly in directions with small eigenvalues. In particular, if $\theta\in\Theta_s(R)$, then $\theta_j^2$ is constrained on the scale $\mu_j^{2s}$. The lower bound will use a block of coordinates where these scales are similar.

Worked Example: Translating a Source Condition

Suppose $\mu_j=j^{-2}$, $r=1/2$, and $\sum_j g_j^2\leq 4$. Then $s=r+1/2=1$, and $$ \theta_j=\sqrt{\mu_j}f_j=\mu_j^{1/2}\mu_j^{1/2}g_j=\mu_j g_j. $$ Consequently, $$ \sum_{j\geq1}\frac{\theta_j^2}{\mu_j^2}=\sum_{j\geq1}g_j^2\leq4. $$ Thus the source condition becomes $\theta\in\Theta_1(2)$. The observation noise acts directly on $\theta_j$, and the prediction loss is $\sum_j(\hat\theta_j-\theta_j)^2$; neither expression has an additional eigenvalue weight.

A Gaussian Testing Fact

The proof compares parameters that differ in just one coordinate. In that coordinate, the observation is normal with the same variance under either parameter, but with two different means. The Kullback–Leibler divergence and total variation distance quantify how difficult it is to tell these distributions apart. Total variation is defined as $\sup_A|P(A)-Q(A)|$, with the supremum over measurable events.

Lemma: Let $P_+$ and $P_-$ be the distributions of $N(\delta,n^{-1})$ and $N(-\delta,n^{-1})$, respectively. Then $$ \operatorname{KL}(P_+,P_-)=2n\delta^2,\qquad \|P_+-P_-\|_{\mathrm{TV}}\leq \sqrt{\operatorname{KL}(P_+,P_-)/2}=\sqrt{n\delta^2}. $$ For any test of which distribution generated the observation, the average probability of error under equal prior probabilities is at least $(1-\|P_+-P_-\|_{\mathrm{TV}})/2$.

For the divergence identity, the log density ratio at $y$ is $2n\delta y$. Its expectation under $P_+$, where $E[Y]=\delta$, is $2n\delta^2$. The distance inequality is Pinsker’s inequality. To see the testing statement, let $A$ be the event that a test chooses $P_+$. Its average error is $$ \frac{P_+(A^c)+P_-(A)}{2} =\frac{1-(P_+(A)-P_-(A))}{2} \geq\frac{1-\|P_+-P_-\|_{\mathrm{TV}}}{2}. $$ Thus small divergence keeps the testing error bounded away from zero.

Worked Example: Testing One Coordinate

Take $\delta=1/(4\sqrt n)$. Then $n\delta^2=1/16$, so the divergence between the two coordinate distributions is $2n\delta^2=1/8$. Pinsker’s inequality gives total variation at most $\sqrt{1/16}=1/4$. Therefore every test has average error at least $(1-1/4)/2=3/8$. If an estimator chooses the wrong sign for the coordinate, its squared error there is at least $\delta^2=1/(16n)$. This converts a testing error into a prediction-risk contribution.

Polynomial Eigenvalue Decay: The Lower Bound

Assume that for constants $c_-,c_+>0$ and $\kappa>0$, $$ c_-j^{-1/\kappa}\leq\mu_j\leq c_+j^{-1/\kappa},\qquad j\geq1. $$ The parameter $\kappa$ controls the rate of eigenvalue decay. The lower bound below depends on $s$, the source-ellipsoid exponent in the definition above, and on $\kappa$.

Theorem: Suppose $R>0$, $s>0$, and the eigenvalues satisfy the polynomial bounds just stated. There is a constant $C>0$, depending only on $R,s,\kappa,c_-$, such that, for all sufficiently large $n$, $$ \mathcal R_n(\Theta_s(R))\geq C n^{-\frac{2s}{2s+\kappa}}. $$

We prove the result by placing a hypercube of signals inside the ellipsoid. Neighboring vertices differ in one coordinate, so the Gaussian testing fact applies to every edge of the cube. The number of coordinates in the cube determines the resulting risk lower bound.

Choose a coordinate block.
For an integer $m$, use $I=\{m+1,\ldots,2m\}$. On this block, all eigenvalues are at least $c_-(2m)^{-1/\kappa}$.

Construct alternatives.
Set $\theta_j^\omega=\delta\omega_j$ for $j\in I$, and zero elsewhere, where each $\omega_j\in\{-1,1\}$ and $\delta=a/\sqrt n$.

Keep the alternatives in the ellipsoid.
Choose $m$ proportional to $n^{\kappa/(2s+\kappa)}$, with a sufficiently small proportionality constant.

Convert testing errors to risk.
Each of the $m$ signs has a probability of error bounded away from zero, and every wrong sign incurs squared error at least $\delta^2$.

Here are the details. For any vertex $\theta^\omega$, the eigenvalue lower bound gives $$ \sum_{j\geq1}\frac{(\theta_j^\omega)^2}{\mu_j^{2s}} \leq m\delta^2\{c_-(2m)^{-1/\kappa}\}^{-2s} =a^2c_-^{-2s}2^{2s/\kappa}n^{-1}m^{1+2s/\kappa}. $$ Set $m=\lfloor\gamma n^{\kappa/(2s+\kappa)}\rfloor$. Since $1+2s/\kappa=(2s+\kappa)/\kappa$, the right-hand side is at most $$ a^2c_-^{-2s}2^{2s/\kappa}\gamma^{1+2s/\kappa}. $$ Choose $\gamma>0$ small enough that this quantity is at most $R^2$. Every vertex then belongs to $\Theta_s(R)$.

Fix a coordinate $j\in I$ and pair each vertex with the vertex that differs only in its $j$-th sign. The distributions of the full observed sequence under this pair have total variation equal to that of the differing coordinate: all other coordinates have the same distribution under both parameters. With $a=1/4$, the lemma bounds that distance by $a$. Consequently, any sign decision based on the full data has average error at least $(1-a)/2=3/8$. If an estimator’s $j$-th coordinate has the wrong sign, its squared error in that coordinate is at least $\delta^2$. Averaging over the $2^m$ vertices and summing over the $m$ coordinates therefore gives $$ \frac{1}{2^m}\sum_\omega E_{\theta^\omega}\|\hat\theta-\theta^\omega\|_2^2 \geq \frac{3}{8}m\delta^2 =\frac{3}{128}\frac{m}{n}. $$ The supremum risk over the ellipsoid is at least this average risk. For sufficiently large $n$, the floor in $m$ implies $m\geq(\gamma/2)n^{\kappa/(2s+\kappa)}$. Taking the infimum over estimators proves the stated lower bound, with a positive constant $C$. $\square$

Worked Example: A Polynomial Spectrum and a Concrete Hypercube

Let $\mu_j=j^{-1}$, $s=1/2$, $R=1$, and $n=10{,}000$. Use coordinates $101,\ldots,200$, so $m=100$, and set $\delta=1/(4\sqrt n)=0.0025$. For any sign vector on this block, the ellipsoid sum is bounded by $$ \delta^2\sum_{j=101}^{200}j =\frac{1}{160{,}000}\left(\frac{100(101+200)}{2}\right) =\frac{15{,}050}{160{,}000} =0.0940625<1. $$ Thus every vertex belongs to the radius-one ellipsoid. For a pair differing in one sign, the divergence is $2n\delta^2=1/8$, so the average testing error is at least $3/8$. The average risk over the hypercube is consequently at least $$ \frac{3}{8}\,m\delta^2 =\frac{3}{8}\cdot100\cdot\frac{1}{160{,}000} =0.000234375. $$ This calculation verifies the construction at this sample size; the general theorem supplies the asymptotic rate $n^{-1/2}$ because $\kappa=1$ and $s=1/2$.

What the Bound Says About Spectral Decay

The lower-bound exponent is $2s/(2s+\kappa)$. Greater source smoothness $s$ makes the ellipsoid narrower in high-index directions, while larger $\kappa$ means the eigenvalues decay more slowly and more directions remain relevant. The theorem says that no estimator can uniformly beat this rate over the stated ellipsoid, up to constants.

The same testing construction also illustrates why the spectral assumption matters. For example, suppose instead that $\mu_j=2^{-j}$, $s=1$, and $R=1$. Let $m=\lfloor(\log_2 n)/8\rfloor$, use coordinates $m+1,\ldots,2m$, and again take $\delta=1/(4\sqrt n)$. Since $\mu_j^{-2}=4^j$, the ellipsoid sum for every vertex is at most $$ \delta^2m\,4^{2m}=\frac{m\,16^m}{16n} \leq \frac{m}{16\sqrt n}. $$ Here $16^m\leq\sqrt n$, by the definition of $m$. For all sufficiently large $n$, $m/(16\sqrt n)\leq1$, so the hypercube lies in the ellipsoid. The same testing argument yields a lower bound proportional to $m/n$, hence to $(\log n)/n$. This example is a separate spectral calculation, not a consequence of the polynomial-spectrum theorem.

Common Pitfall

A common mistake is to use the source condition $f_j=\mu_j^r g_j$ and then treat $f_j$ itself as the coordinate with unweighted prediction loss. That drops the eigenvalue weight in the loss. Prediction error is $\sum_j\mu_j(\hat f_j-f_j)^2$; after setting $\theta_j=\sqrt{\mu_j}f_j$, it becomes $\sum_j(\hat\theta_j-\theta_j)^2$. The corresponding ellipsoid exponent is $s=r+1/2$, not $r$. Leaving out this half-power changes the lower-bound rate.

A second error is to infer a minimax upper bound from the lower bound. The theorem only proves that all estimators face a minimum level of worst-case risk. To claim that a particular procedure achieves the minimax rate requires a matching upper bound; the lower-bound argument by itself does not establish that claim.

Check Your Understanding

Work through these questions using the definitions and argument above.

Under $f_j=\mu_j^r g_j$, why does prediction-coordinate scaling produce the ellipsoid exponent $s=r+1/2$?
For polynomial eigenvalues $\mu_j\asymp j^{-1/\kappa}$, what block size balances the ellipsoid constraint with noise of variance $1/n$?
Why does a wrong sign decision on a coordinate with true value $\delta$ contribute at least $\delta^2$ to squared error?
In the theorem’s proof, which choice ensures that neighboring Gaussian alternatives remain difficult to distinguish?
What additional result would be needed to conclude that a particular estimator is minimax-rate optimal?