Le Cam and Fano Lower Bound Methods

Two recipes for proving no estimator beats a floor. Le Cam reduces to two hard cases, Fano to many packed cases, and information bounds the testing error both ways.

$Two close distributions force error past half their distance while a large packed set forces error through information limits$

Two close distributions force error past half their distance while a large packed set forces error through information limits

Why Does This Exist?

Minimax theory needs floors, and floors need proofs that every estimator fails somewhere. Direct analysis over all estimators is impossible, so both methods reduce estimation to hypothesis testing: if estimators were accurate, they would induce accurate tests, and testing has sharp information limits. Bound the test, bound the estimators.

Le Cam handles two-point reductions with total variation or Hellinger distance: two close parameters nobody can reliably tell apart. Fano handles many-point packings with mutual information: exponentially many separated parameters nobody can jointly identify. Together they prove nearly every sparse, nonparametric and high-dimensional floor in use.

Prerequisite in one paragraph. You need KL divergence $D(P\|Q)$ (how distinguishable $Q$ is from $P$ ) and total variation distance (the best test advantage). Packing counts separated points as in covering theory. Background is in Kullback-Leibler divergence and covering and packing numbers.

Think of It Like This

Two lookalikes versus a lineup of hundreds

To prove a witness is unreliable, show two suspects so alike that nobody tells them apart half the time. That is Le Cam: one hard pair forces error past half their separation. To prove a harder task impossible, parade hundreds of lookalikes past the witness and count how much information each glimpse carries. That is Fano: too many faces, too little information per view, so the identification error stays large.

Both argue through testing, not estimation. The witness never estimates height; they pick a face. Estimation inherits the failure because a good estimate would pick correctly.

Where the analogy stops: witnesses tire and faces move, while the theorems assume fixed distributions and optimal tests. The bounds are generous to the statistician, which makes them valid floors.

How It Actually Works

Le Cam's two-point bound: for parameters $\theta_0, \theta_1$ with distributions $P_0, P_1$ and loss metric $d$ , any estimator satisfies $\sup_\theta E[\ell] \ge (d(\theta_0,\theta_1)^2/8)(1 - \mathrm{TV}(P_0, P_1))$ , where $\mathrm{TV}$ is total variation distance (test advantage). Close distributions with $\mathrm{TV} \le 1/2$ force error of order the squared separation.

Fano's bound: pack $M$ parameters pairwise separated by at least $2\delta$ with average KL to a centre bounded by $\beta$ . Then any estimator has worst error at least $\delta^2(1 - (\beta + \log 2)/\log M)$ . Many points ( $\log M$ large) with small information ( $\beta$ small) force large error. The art is building packings with large $\log M$ but small KL, for example Varshamov-Gilbert binary codes for sparsity.

Worked example

Sparse means with $d = 1000$ , $s = 10$ , $n = 1500$ unit-noise samples. A Gilbert packing gives $M$ with $\log M \ge (s/8)\ln(d/s) \approx 1.25 \times 4.61 \approx 5.76$ nats per effective block, scaled to about $46$ nats total across the construction, while $n$ samples cap the information at order $n\delta^2$ per coordinate. Balancing $\beta \approx (\log M)/2$ yields separation $\delta \approx 0.08$ in Euclidean norm after the standard $s\log(d/s)/n$ algebra: $10 \times 4.61/1500 \approx 0.0307$ under the root with Fano constants gives floor $0.08$ .

Le Cam alone with two $10$ -sparse vectors differing in one coordinate of size $0.10$ gives a weaker floor near $0.03$ : it captures one-coordinate hardness but misses the combinatorial price of choosing which $10$ of $1{,}000$ . Fano earns the $\log(d/s)$ factor; Le Cam cannot.

Watch Out For

Packing in the wrong metric for the loss

A packing separated in Hamming distance with tiny Euclidean gaps proves nothing for squared error. The separation must be measured in the loss metric at size $2\delta$ , with KL computed on the induced distributions. Mismatched metrics produce floors in units the estimator never pays.

Fix: build the packing, verify pairwise loss separation, then bound information. All three in the same units.

Letting KL grow with the packing

Adding more points by spreading them wider raises $\beta$ alongside $\log M$ and the Fano ratio $(\beta + \log 2)/\log M$ stays near $1$ , giving a vacuous bound near zero. Bigger packings only help when information per point stays capped.

Fix: fix the radius first from the sample budget, then pack inside it. If $\beta$ exceeds $\log M / 2$ , shrink the separation and try again.

The Quick Version

Estimation floors reduce to testing: good estimates would make good tests.
Le Cam uses one hard pair and total variation; Fano uses many packed points and mutual information.
Fano earns the $\log(d/s)$ factor for sparsity that two-point arguments miss.
At 10 in 1000 with 1500 samples the floor sits near 0.08 Euclidean error.
Pack in the loss metric and cap KL, or the bound goes vacuous.