From a Packing to a Risk Lower Bound
A minimax lower bound can be built by selecting finitely many parameters that are far apart under the loss of interest, while making their corresponding data distributions difficult to distinguish. If an estimator had small risk at every selected parameter, it could be used to identify which parameter generated the data. Fano’s inequality limits the accuracy of that identification when the distributions carry little information about the selected index.
The proof has three quantitative ingredients: a packing separation, an upper bound on information in the data, and a conversion from testing error to estimation loss. The constants matter. In particular, Euclidean separation must be computed from the actual coordinate differences in the packing.
Suppose an estimator \(\hat\theta\) takes values in a space with metric \(\rho\), and its loss is \(\rho(\hat\theta,\theta)^q\), where \(q>0\). The minimax risk over a parameter set containing the packing is at least the largest risk among its packing points. The following result gives a concrete bound.
Proof of the Packing Bound
Give the index \(J\) the uniform distribution on \(\{1,\ldots,M\}\), and, conditional on \(J=i\), draw the data \(Z\) from \(P_i\). From any estimator construct a decoder \(\hat J(Z)\) by choosing an index whose parameter is nearest to \(\hat\theta(Z)\), breaking ties by the smallest index. Because the packing is finite, this is measurable whenever the estimator is measurable.
If \(\hat J\ne J\), then \(\rho(\hat\theta,\theta_J)\geq\Delta/2\). Indeed, if instead \(\rho(\hat\theta,\theta_J)<\Delta/2\), then for every \(j\ne J\), the triangle inequality gives \(\rho(\hat\theta,\theta_j)\geq\rho(\theta_J,\theta_j)-\rho(\hat\theta,\theta_J)>\Delta/2>\rho(\hat\theta,\theta_J)\). Thus \(\theta_J\) is the unique nearest packing point, and the decoder is correct. Consequently, $$ \max_i E_i[\rho(\hat\theta,\theta_i)^q] \geq \frac{1}{M}\sum_{i=1}^M E_i[\rho(\hat\theta,\theta_i)^q] \geq \left(\frac{\Delta}{2}\right)^q P(\hat J\ne J). $$
Fano’s inequality states that for a uniform \(J\) and any decoder, \(P(\hat J\ne J)\geq 1-(I(J;Z)+\log 2)/\log M\). To recall the argument, let \(E\) indicate whether the decoder makes an error. Conditional entropy satisfies \(H(J\mid Z)\leq H(E\mid Z)+H(J\mid E,Z)\leq\log 2+P(E=1)\log(M-1)\). Since \(\log(M-1)\leq\log M\) and \(I(J;Z)=\log M-H(J\mid Z)\), rearranging gives the stated inequality.
It remains to relate mutual information to the reference distribution. Let \(\bar P=M^{-1}\sum_iP_i\). Using densities with respect to a common dominating measure, expand the logarithms to obtain $$ \frac{1}{M}\sum_{i=1}^M D_{\mathrm{KL}}(P_i\|Q) = I(J;Z)+D_{\mathrm{KL}}(\bar P\|Q) \geq I(J;Z). $$ The last inequality uses nonnegativity of Kullback–Leibler divergence. Substituting this upper bound on \(I(J;Z)\) into Fano’s inequality, and then into the risk bound above, proves the theorem. Taking the positive part is valid because a risk is nonnegative. \(\square\)
A useful consequence is immediate. If \(M\geq8\) and the average reference divergence is at most \((\log M)/8\), then $$ P(\hat J\ne J)\geq 1-\frac18-\frac{\log2}{\log M}\geq 1-\frac18-\frac13=\frac{13}{24}. $$ Thus the minimax risk is at least \((\Delta/2)^q(13/24)\). The condition on divergence is sufficient, not necessary; other constants can be used when they give a positive error bound.
Worked Gaussian Examples
Worked Example: Eight Gaussian Means and the Numerical Constant
Let \(n\) independent observations be four-dimensional normal vectors with covariance matrix \(I_4\). Use as eight candidate mean vectors \(\mu_j=a v_j\), where \(v_j\) ranges over the eight binary vectors in \(\{0,1\}^4\) having an even number of ones. Estimate the mean under squared Euclidean loss.
Any two distinct even-parity vectors differ in at least two coordinates, so the candidate means have separation \(\Delta\geq a\sqrt{2}\). Each vector has at most four ones, hence \(\|\mu_j\|_2^2\leq4a^2\). Take \(Q\) to be the law of \(n\) independent \(N(0,I_4)\) observations. The Gaussian mean-shift divergence is \(n\|\mu_j\|_2^2/2\), so \(D_{\mathrm{KL}}(P_j\|Q)\leq2na^2\).
Set \(a^2=\log(8)/(16n)\). Then every reference divergence is at most \(\log(8)/8\), and \(M=8\) gives error probability at least \(13/24\). Since \((\Delta/2)^2\geq a^2/2\), the theorem yields $$ \inf_{\hat\mu}\max_j E_j\|\hat\mu-\mu_j\|_2^2 \geq \frac{a^2}{2}\frac{13}{24} =\frac{13a^2}{48} =\frac{13\log 8}{768n} \approx \frac{0.0352}{n}. $$ For the decimal, \(\log 8\approx2.0794415\), so \(13\log 8/768\approx0.0351989\). This calculation illustrates why a reported numerical constant should be recomputed from the exact expression.
Worked Example: A Bernoulli Product Packing
For \(j=1,\ldots,8\), let \(\theta_j=\varepsilon e_j\in\mathbb{R}^8\), where \(e_j\) is the \(j\)th coordinate vector. One observation has eight independent Bernoulli coordinates, with coordinate \(\ell\) having success probability \(1/2+\theta_\ell\). Take \(n\) independent observations and estimate \(\theta\) under squared Euclidean loss.
For distinct \(j,k\), \(\|\theta_j-\theta_k\|_2=\sqrt{2}\varepsilon\), so \(\Delta=\sqrt{2}\varepsilon\). Use the reference law \(Q\) under which all coordinates have success probability \(1/2\). For one changed coordinate, the Bernoulli divergence is bounded by its chi-squared divergence: \(D_{\mathrm{KL}}(\operatorname{Ber}(1/2+\varepsilon)\|\operatorname{Ber}(1/2))\leq4\varepsilon^2\). Indeed, \(D_{\mathrm{KL}}(P\|Q)\leq\chi^2(P,Q)\), and here \((\varepsilon^2/(1/2))+(\varepsilon^2/(1/2))=4\varepsilon^2\). Independence and \(n\) repetitions therefore give \(D_{\mathrm{KL}}(P_j\|Q)\leq4n\varepsilon^2\).
Choose \(\varepsilon^2=\log(8)/(32n)\), which also ensures valid probabilities for \(n\geq1\). The divergence is at most \(\log(8)/8\), so the error probability is at least \(13/24\). The squared-risk lower bound is $$ \left(\frac{\sqrt{2}\varepsilon}{2}\right)^2\frac{13}{24} =\frac{\varepsilon^2}{2}\frac{13}{24} =\frac{13\log(8)}{1536n}. $$ This example shows how a coordinatewise divergence bound can control a product experiment without requiring the candidate distributions to be pairwise compared directly.
A Dimension-Dependent Risk Regime
Worked Example: A Hypercube Packing Gives a \(d/n\) Bound
Consider estimating \(\mu\in\mathbb{R}^d\) from \(n\) independent \(N(\mu,I_d)\) observations, under squared Euclidean loss. We first produce a binary packing. A greedy construction selects binary vectors and removes all vectors within Hamming distance \(\lfloor d/4\rfloor\) of each selection. The selected vectors have pairwise Hamming distance greater than \(d/4\). If \(B=\sum_{j=0}^{\lfloor d/4\rfloor}\binom{d}{j}\) is the number removed at each selection, the construction selects at least \(2^d/B\) vectors.
Writing \(h(t)=-t\log t-(1-t)\log(1-t)\), the binomial bound gives \(B\leq(d+1)\exp(dh(1/4))\). Since \(\log 2-h(1/4)>0.13\), for all sufficiently large \(d\) the packing has \(M\geq\exp(\kappa d)\) points with, for example, \(\kappa=0.1\). Increase the dimension threshold if needed so that \(M\geq8\).
For each selected vector \(v\in\{0,1\}^d\), set \(\mu_v=av\). A Hamming distance greater than \(d/4\) gives \(\|\mu_v-\mu_w\|_2^2=a^2\,d_H(v,w)>a^2d/4\), hence Euclidean separation greater than \(a\sqrt d/2\). Also \(\|\mu_v\|_2^2\leq a^2d\). Relative to \(n\) observations from \(N(0,I_d)\), the divergence satisfies \(D_{\mathrm{KL}}(P_v\|Q)=n\|\mu_v\|_2^2/2\leq na^2d/2\).
Take \(a^2=c/(2n)\), with \(c=\kappa/4\). Then the divergence is at most \(cd/4=\kappa d/16\leq(\log M)/16\). Since \(M\geq8\), Fano’s inequality gives \(P(\hat J\ne J)\geq1-1/16-1/3=29/48>1/2\). Using the valid separation \(\delta=a\sqrt d/2\), the squared-risk bound is therefore $$ \inf_{\hat\mu}\max_v E_v\|\hat\mu-\mu_v\|_2^2 \geq \frac12\left(\frac{\delta}{2}\right)^2 =\frac{a^2d}{32} =\frac{cd}{64n}. $$ Thus this construction gives a risk regime proportional to \(d/n\), for sufficiently large \(d\), with the stated Gaussian model and squared-error loss. The constants here are conservative; the point is that packing size grows exponentially in dimension while each candidate remains close enough to the reference law for Fano’s inequality to apply.
What the Bound Does and Does Not Say
A packing argument is useful when the parameter space contains many separated points, but the data distributions at those points are not too informative about their labels. The number of packing points contributes through \(\log M\); the separation contributes through \((\Delta/2)^q\). A positive Fano factor is essential. If the average divergence bound is too large relative to \(\log M\), this version of the argument gives no positive lower bound, and a different packing, reference distribution, or lower-bound method may be needed.
Common mistake: overstating Euclidean separation. For binary vectors \(v,w\), the squared distance between \(av\) and \(aw\) is \(a^2d_H(v,w)\), not \(4a^2d_H(v,w)\). Thus Hamming separation greater than \(d/4\) implies Euclidean separation greater than \(a\sqrt d/2\), not \(a\sqrt d\). The factor of two in distance becomes a factor of four in squared loss. In the dimension-dependent example, using the correct \(\delta=a\sqrt d/2\) gives \(a^2d/32=cd/(64n)\); the larger separation would incorrectly inflate the risk bound by a factor of four.
A second practical check is to keep the reference law fixed while computing all divergences, and to use the same loss metric for both packing separation and risk. The theorem does not require pairwise divergences to be small; it requires an average divergence to a common reference distribution to be small. This can make the information calculation substantially simpler.
Check Your Understanding
Use the definitions and proof above to answer the following questions.
- Why does an estimator within distance strictly less than \(\Delta/2\) of the true packing point identify that point as the unique nearest one?
- In the theorem, what does the average divergence from \(Q\) control, and why is a common reference distribution useful?
- For eight hypotheses with average divergence at most \((\log 8)/8\), calculate the Fano lower bound on decoding error.
- If binary vectors have Hamming distance greater than \(d/4\) and parameters are \(av\), what lower bound follows for their Euclidean separation?
- What happens to the theorem’s risk conclusion if the bracketed Fano factor is nonpositive?