Three Constructions, Three Geometries
A minimax lower bound begins with a choice: which parameter values should be made difficult to distinguish? A pair of alternatives is economical and often enough when the parameter contains one hard direction. A large separated family can exploit the number of plausible alternatives. A hypercube is useful when many coordinates can each be made difficult, so their errors accumulate. The construction should reflect the geometry of the parameter and the way the observation distributions change with it.
The methods share a common structure. Pick parameter values whose estimation errors would be substantial, show that the corresponding data distributions are hard to distinguish, and translate testing error into estimation risk. The challenge is not to use the most elaborate method; it is to find a construction whose separation and distinguishability can both be controlled.
The three choices can be summarized by what they count. Le Cam’s method counts one difficult distinction. Fano’s method counts mistakes among many separated possibilities. Assouad’s method counts coordinate errors across neighboring vertices of a cube.
| Method | Parameter geometry | Useful when | Main quantity to control |
|---|---|---|---|
| Le Cam | Two points separated by \(\Delta\) | One direction already gives the desired scale | Distance between the two data laws |
| Fano | A finite, well-separated packing | There are many plausible parameter values | Information about the packing label |
| Assouad | A hypercube of coordinate choices | Errors across many coordinates should add | Distinguishability of neighboring vertices |
What Each Method Guarantees
For two probability distributions \(P\) and \(Q\), their total variation distance is \(\operatorname{TV}(P,Q)=\sup_A|P(A)-Q(A)|\). It measures the best possible difference in rejection probabilities for a test. The following two-point bound makes the geometry-to-risk conversion explicit.
To see the reduction, turn \(\hat\theta\) into a test that selects whichever of \(\theta_0,\theta_1\) is closer to \(\hat\theta\), breaking ties in a fixed way. If that test is wrong, the triangle inequality implies the estimator is at least \(\Delta/2\) from the true point. For any test, the sum of its two error probabilities is at least \(1-\operatorname{TV}(P_{\theta_0},P_{\theta_1})\). Therefore the sum of the two risks is at least \((\Delta/2)(1-\operatorname{TV})\); their maximum is at least half this sum. This proves the bound. \(\square\)
For many alternatives, suppose \(\theta_1,\ldots,\theta_M\) are pairwise at distance at least \(\Delta\), with \(M\ge2\). Any estimator can be converted to a decoder by choosing the nearest packing point. If the decoder is wrong, the estimator’s distance from the truth is at least \(\Delta/2\): otherwise the triangle inequality would make the true packing point strictly closer than every other one. Fano’s inequality therefore gives the following risk bound.
The factor \(\Delta/2\) is the same nearest-point argument as above; the distinct feature is that Fano controls the probability of decoding the wrong label among \(M\) choices. The reference-law inequality is useful when the alternatives all have manageable divergence from a common distribution, even if pairwise calculations are less convenient.
For a hypercube, index parameters by \(v\in\{0,1\}^m\). Suppose a decoder \(\hat v\) can be formed from any estimator so that, for every vertex \(v\), $$ d(\hat\theta,\theta_v)\ge c\,H(\hat v,v), $$ where \(H\) is Hamming distance and \(c>0\). Assouad’s argument pairs vertices that differ only in coordinate \(j\). Write \(P_v\) for the data law at vertex \(v\), and let \(\operatorname{TV}_{\max}\) be the largest total variation distance over all such neighboring pairs. Averaging uniformly over vertices gives $$ 2^{-m}\sum_v E_v[H(\hat v,v)] \ge \frac{m}{2}(1-\operatorname{TV}_{\max}). $$ Indeed, for a fixed coordinate \(j\), pair each vertex with \(v_j=0\) to the vertex with the same other bits and \(v_j=1\). The two possible errors in deciding that bit have sum at least \(1-\operatorname{TV}(P_v,P_{v^{(j)}})\). There are \(2^{m-1}\) pairs, and dividing their summed error probabilities by \(2^m\) gives an average error probability at least \((1-\operatorname{TV}_{\max})/2\) for that coordinate. Summing over the \(m\) coordinates proves the display. Consequently, $$ \sup_v E_v[d(\hat\theta,\theta_v)] \ge \frac{cm}{2}(1-\operatorname{TV}_{\max}). $$ This bound is valuable when the loss genuinely accumulates across coordinates.
Worked Examples: Match the Construction to the Model
Worked Example: A Two-Point Gaussian Location Bound
Observe \(n\) independent variables with distribution \(N(\theta,1)\), and use absolute-error loss. Compare \(\theta_0=-\delta/2\) and \(\theta_1=\delta/2\), where \(\delta=1/\sqrt n\). The two parameter values are separated by \(\Delta=\delta\).
For normal distributions with common variance \(1\), the Kullback–Leibler divergence between the \(n\)-observation laws is $$ \operatorname{KL}(P_{\theta_0}\Vert P_{\theta_1}) =\frac{n(\theta_0-\theta_1)^2}{2} =\frac{n\delta^2}{2} =\frac12. $$ Pinsker’s inequality, \(\operatorname{TV}(P,Q)\le\sqrt{\operatorname{KL}(P\Vert Q)/2}\), gives \(\operatorname{TV}(P_{\theta_0},P_{\theta_1})\le1/2\). Applying the two-point bound, $$ \sup_{\theta\in\{\theta_0,\theta_1\}}E_\theta|\hat\theta-\theta| \ge \frac{\delta}{4}(1-\operatorname{TV}) \ge \frac{1}{8\sqrt n}. $$ The pair is enough: it exposes a single location direction at the \(n^{-1/2}\) scale. A packing would add complexity without being needed for this basic lower-bound scale.
Worked Example: Many Orthogonal Gaussian Means
Observe one vector \(X\in\mathbb R^M\) with \(X\sim N(\theta,I_M)\). Use Euclidean loss and consider \(M\) alternatives \(\theta_j=a e_j\), where \(e_j\) is the \(j\)th coordinate vector and \(a^2=(\log M)/4\). For distinct \(j,k\), $$ \|\theta_j-\theta_k\|_2=\sqrt{2}\,a, $$ so these points form a packing with \(\Delta=\sqrt{2}\,a\).
Take \(Q=N(0,I_M)\) as the reference law. The Gaussian divergence formula gives $$ \operatorname{KL}(P_{\theta_j}\Vert Q) =\frac{\|\theta_j\|_2^2}{2} =\frac{a^2}{2} =\frac{\log M}{8}. $$ Thus \(I(J;X)\le(\log M)/8\). If \(M\ge16\), then \(\log 2/\log M\le1/4\), so the Fano error factor is at least $$ 1-\frac{I(J;X)+\log 2}{\log M} \ge 1-\frac18-\frac14=\frac58. $$ The risk is therefore at least $$ \frac{\sqrt{2}\,a}{2}\cdot\frac58 =\frac{5a}{8\sqrt2} =\frac{5\sqrt{\log M}}{16\sqrt2}. $$ Here the alternatives differ by which coordinate carries the signal. The many-way identification problem uses the size of the packing; a single pair would not express that feature.
Worked Example: Coordinatewise Difficulty in a Bernoulli Hypercube
For each \(v\in\{0,1\}^m\), observe independent \(X_1,\ldots,X_m\), with \(X_j\sim\operatorname{Bernoulli}(1/2+\alpha)\) if \(v_j=1\) and \(X_j\sim\operatorname{Bernoulli}(1/2-\alpha)\) if \(v_j=0\). Take \(\alpha=1/8\), estimate the vector of success probabilities, and use \(\ell_1\) loss.
Decode coordinate \(j\) as 1 when the estimated probability is at least \(1/2\), and as 0 otherwise. Whenever this bit is wrong, its absolute estimation error is at least \(\alpha=1/8\). Thus the \(\ell_1\) loss is at least \((1/8)H(\hat v,v)\).
Neighboring vertices differ in exactly one Bernoulli coordinate. The common distribution of the other coordinates does not change the total variation distance, so it suffices to calculate the divergence for one Bernoulli observation. In either direction it is $$ \operatorname{KL}\bigl(\operatorname{Bernoulli}(5/8)\Vert \operatorname{Bernoulli}(3/8)\bigr) =\frac14\log(5/3). $$ Pinsker’s inequality gives $$ \operatorname{TV}_{\max}\le \sqrt{\frac18\log(5/3)}<\frac12, $$ where the final inequality follows from \(\log(5/3)<2\). Assouad’s bound now yields $$ \sup_v E_v\|\hat\theta-\theta_v\|_1 \ge \frac18\cdot\frac{m}{2}(1-\operatorname{TV}_{\max}) > \frac{m}{32}. $$ The construction is effective because each of the \(m\) coordinate decisions has a neighboring alternative with bounded distinguishability, and each wrong decision contributes to the total loss.
A Practical Selection Rule
Start with the parameter geometry, not with a favorite inequality. If one path through the parameter space already gives the scale you need, choose two alternatives and use Le Cam. If the problem has many well-separated possibilities and a common reference distribution gives a clean average divergence bound, use Fano. If the loss can be lower-bounded by the number of incorrect coordinate decisions and neighboring vertices remain hard to distinguish, use Assouad.
Ask whether separation is naturally one-dimensional, packing-like, or additive across coordinates.
A simple pair can be sharper and easier to verify than a larger family if it already captures the needed difficulty.
Calculate the relevant total variation or information bound, including the sample size and all coordinates that change.
State why a testing or decoding error forces a specified amount of estimation loss; the conversion depends on the metric and construction.
A common mistake is to conclude that more alternatives always yield a stronger lower bound. A large packing with very small separation, or one whose distributions are easy to identify, may give less than a carefully chosen pair. Similarly, a hypercube does not automatically produce a factor of \(m\): that accumulation requires a loss-to-Hamming inequality and hard neighboring distributions. The construction, separation, divergence calculation, and loss conversion must work together.
These methods are complementary rather than competing. A pair isolates one obstruction; Fano captures uncertainty among many separated parameters; Assouad aggregates many local obstructions. Choosing among them is a matter of matching the geometry of the statistical problem to the structure of the risk.
Check Your Understanding
For each question, identify the geometry or calculation that should guide the choice of lower-bound method.
- A scalar parameter has two candidate values separated by \(\Delta\), and their data laws have small total variation. Which method is the most direct, and what risk conversion does it use?
- Why can a family of \(M\) separated parameters make Fano’s method useful even when no single pair captures the main difficulty?
- In an Assouad construction, what two conditions are needed to turn coordinatewise testing difficulty into a lower bound for estimation loss?
- For the Gaussian packing example, what is the pairwise Euclidean separation between \(a e_j\) and \(a e_k\) when \(j\ne k\)?
- Why does increasing the number of alternatives not, by itself, guarantee a stronger minimax lower bound?