Fano information lower bounds

To prove that no algorithm can beat a certain error — a lower bound, the hard direction of optimality — you show that the data simply does not contain enough information to tell apart many genuinely different possibilities. Fano's method makes this rigorous: plant a large collection of well-separated candidate truths that are nonetheless statistically hard to distinguish, and argue that any estimator must confuse some of them and so incur error. It converts the claim that estimation is hard into the claim that testing among many hypotheses is hard.

Reduce estimation to multiway hypothesis testing over a finite packing of the parameter space whose members are pairwise far in the loss metric but close in distribution. Fano's inequality then lower-bounds the probability of test error in terms of the mutual information, or average divergence, between the data and the index, divided by the logarithm of the packing size. When the candidates are mutually uninformative — small divergence — yet numerous and well-separated, no estimator can reliably identify the true one, forcing a lower bound on the minimax risk. Le Cam's two-point method is the two-hypothesis special case; Assouad's lemma is the hypercube version.

Fano's method is the central engine for minimax lower bounds across nonparametric estimation, density estimation, and increasingly the statistical limits of machine learning — sparse recovery, matrix completion, and the sample complexity of learning. It certifies that an estimator achieving a matching upper bound is optimal, not merely the best one tried. The craft lies in constructing the packing: too few or too close, and the bound is weak; the art is maximizing separation in loss while minimizing distinguishability in information.