Information-theoretic minimax lower bounds

For squared Euclidean loss, minimax risk takes the infimum over estimators of their worst expected error over the parameter class. A lower bound can restrict attention to a finite subset because the worst case over the full class is at least the worst case over that subset. Choose hypotheses separated by at least twice a radius. If an estimator lands within that radius of the truth, nearest-neighbor decoding identifies the correct hypothesis. A testing error therefore implies that the estimation error is at least the radius.

This reduction requires the metric used to separate hypotheses to match the loss being bounded. Prediction loss in a design image is not automatically equivalent to coefficient loss, just as support error is not the same as Euclidean error. The finite subset must also lie entirely in the advertised parameter class: a lower bound using dense alternatives does not establish a sparse-class lower bound. These bookkeeping conditions are part of the argument rather than details to fill in after applying an information inequality.

Let the hypothesis index be uniform on $M\geq2$ alternatives and let the data follow the corresponding distribution. Fano’s inequality bounds average decoding error below by one minus mutual information plus a binary entropy constant divided by the logarithm of the number of alternatives. All logarithms here are natural. Mutual information can be bounded above by the average divergence from any fixed reference distribution when those divergences are finite. Choosing the reference well avoids unnecessary calculations with the mixture distribution.

Combining Fano with the separation argument gives the displayed expected-risk lower bound, with a nonpositive bracket understood as the trivial zero bound. There is a balance: increasing hypothesis separation improves the loss scale but also increases divergence and makes testing easier. Increasing the packing size supplies more uncertainty about the index, but the parameter class limits how many well-separated points fit. A valid proof chooses amplitude and packing together rather than inserting arbitrary large signals into a convenient entropy formula.

In the Gaussian sequence model over vectors with at most $s$ nonzero coordinates, for $1\leq s\leq p/2$, the squared Euclidean minimax risk is of order $\sigma^2s\log(ep/s)/n$, up to universal constants. A sparse packing captures both unknown values and unknown support. Corresponding upper bounds show that this is a statistical benchmark for that experiment. Transporting the rate to a regression design requires conditions connecting its measurement geometry to the coefficient metric; a singular unrestricted design can invalidate such a transfer.

An information-theoretic lower bound includes computationally unbounded estimators and therefore cannot by itself establish a computational hardness gap. Nor does a Euclidean minimax rate imply exact support recovery: arbitrarily small nonzero coefficients remain compatible with that class. A fixed-dimensional two-point construction can also miss a logarithmic dimension penalty, so many-hypothesis arguments are often needed. The practical value of a lower bound is its precise scope: it tells whether improving an estimator’s rate is statistically possible under the stated experiment, class, and loss.