Fano’s Method for Metric Estimation

From Estimation to Identification

A minimax lower bound for estimating a parameter can be difficult to obtain by studying every possible parameter value at once. A useful alternative is to select a finite collection of well-separated parameters. If an estimator is accurate enough to distinguish the selected points, then it also solves a finite-hypothesis identification problem. Fano’s inequality limits how often that identification can succeed when the data contain little information about which point generated them.

The key conversion has two parts. First, decode an estimator by assigning it to the nearest point in the selected collection. Second, observe that a decoding error forces the estimate to be at least half the packing separation away from the true parameter. This turns a lower bound on error probability into a lower bound on expected metric loss.

Definition: Let $(\Theta,d)$ be a metric parameter space. A finite set $\{\theta_1,\ldots,\theta_M\}\subseteq\Theta$ is $\delta$-separated if $d(\theta_j,\theta_k)\geq\delta$ whenever $j\neq k$. For an estimator $\hat\theta$, its metric risk at $\theta$ is $R(\theta,\hat\theta)=E_\theta[d(\hat\theta,\theta)]$, and its minimax risk over $\Theta$ is $\inf_{\hat\theta}\sup_{\theta\in\Theta}R(\theta,\hat\theta)$.

Assume the estimator takes values in a metric space where the distances to the parameters are defined, and that it is measurable. For each data value, choose a nearest point among the finite packed set; if several points are equally near, choose the one with the smallest index. This defines a measurable decoder because it makes a finite number of measurable distance comparisons.

Fano’s inequality: Let $J$ be uniform on $\{1,\ldots,M\}$, with $M\geq2$, and, conditional on $J=j$, let the data $Z$ have distribution $P_j$. For any measurable decoder $\hat J(Z)$, its error probability $P_e=P(\hat J\neq J)$ satisfies $$ P_e\geq 1-\frac{I(J;Z)+\log 2}{\log M}, $$ where $I(J;Z)$ is the mutual information. Since an error probability is nonnegative, the bound can be replaced by its positive part when the displayed right-hand side is negative.

The Metric Fano Bound

For each packed parameter $\theta_j$, let $P_j$ denote the distribution of the data. Draw $J$ uniformly from the $M$ indices, then draw $Z$ from $P_J$. Given an estimator $\hat\theta(Z)$, define $\hat J$ to be the index of the nearest packed parameter to $\hat\theta(Z)$.

Theorem: Suppose $\{\theta_1,\ldots,\theta_M\}$ is a $\delta$-separated subset of $\Theta$, with $M\geq2$. For any estimator with finite metric risk, $$ \inf_{\hat\theta}\sup_{\theta\in\Theta}E_\theta[d(\hat\theta,\theta)] \geq \frac{\delta}{2}\left[1-\frac{I(J;Z)+\log 2}{\log M}\right]_+, $$ where $J$ is uniform on the packed indices, $Z\mid J=j\sim P_j$, and $[x]_+=\max\{x,0\}$. The inequality holds for every estimator separately, so the right-hand side is a lower bound on minimax risk.

Proof. Fix an estimator and use its nearest-point decoder. Suppose that the true index is $J=j$, but the decoder returns $k\neq j$. By the definition of a nearest point, $d(\hat\theta,\theta_k)\leq d(\hat\theta,\theta_j)$. The triangle inequality and separation therefore give $$ \delta\leq d(\theta_j,\theta_k) \leq d(\theta_j,\hat\theta)+d(\hat\theta,\theta_k) \leq 2d(\hat\theta,\theta_j). $$ Thus $d(\hat\theta,\theta_J)\geq\delta/2$ whenever decoding is wrong. Taking expectations under the uniform choice of $J$ yields $$ \frac{1}{M}\sum_{j=1}^M E_{\theta_j}[d(\hat\theta,\theta_j)] \geq \frac{\delta}{2}P_e. $$ The supremum risk over $\Theta$ is at least this average over the finite subset. Fano’s inequality lower-bounds $P_e$; if its right-hand side is negative, use the trivial bound $P_e\geq0$. Taking the infimum over estimators proves the result. $\square$

A convenient way to use the theorem is to bound mutual information using a reference distribution $Q$. If every $P_j$ is absolutely continuous with respect to $Q$ and the average divergence is finite, then $$ I(J;Z)\leq \frac{1}{M}\sum_{j=1}^M \operatorname{KL}(P_j\|Q). $$ Here $\operatorname{KL}(P\|Q)$ denotes the Kullback–Leibler divergence. To verify the inequality, let $\bar P=M^{-1}\sum_jP_j$ be the mixture distribution. The mutual information equals $M^{-1}\sum_j\operatorname{KL}(P_j\|\bar P)$. Subtracting this expression from the average divergence to $Q$, and writing densities relative to a common dominating measure, gives $$ \frac{1}{M}\sum_{j=1}^M\operatorname{KL}(P_j\|Q)-I(J;Z) =\operatorname{KL}(\bar P\|Q)\geq0. $$ The final inequality is nonnegativity of Kullback–Leibler divergence. Consequently, a usable form of the metric bound is $$ \inf_{\hat\theta}\sup_{\theta\in\Theta}E_\theta[d(\hat\theta,\theta)] \geq \frac{\delta}{2}\left[1- \frac{M^{-1}\sum_{j=1}^M\operatorname{KL}(P_j\|Q)+\log 2}{\log M} \right]_+. $$ Choosing $Q$ is a matter of convenience: it need not itself correspond to a parameter in the packing.

Worked Applications

Worked Example: A Five-Point Packing with a Given Divergence Bound

Suppose a parameter space contains five points separated by at least $\delta=0.5$. For their data distributions, suppose a reference distribution $Q$ satisfies $5^{-1}\sum_{j=1}^5\operatorname{KL}(P_j\|Q)=0.25$. Find the resulting lower bound on minimax metric risk.

The information bound gives $I(J;Z)\leq0.25$. Using natural logarithms, Fano’s inequality therefore yields $$ P_e\geq 1-\frac{0.25+\log 2}{\log 5} =1-\frac{0.943147\ldots}{1.609438\ldots} \approx 0.4140. $$ The metric conversion contributes the factor $\delta/2=0.25$. Hence the minimax risk is at least $$ \frac{0.5}{2}(0.4140\ldots)\approx 0.1035. $$ This conclusion applies to estimation over the full parameter space, because its worst-case risk is at least its average risk on these five selected points.

Worked Example: Gaussian Location Parameters

Let $Z=(X_1,\ldots,X_n)$, where the $X_i$ are independent and $X_i\sim N(\theta,\sigma^2)$. Select four parameters $\theta_j=ja$, for $j=0,1,2,3$, with $a=\sigma/(5\sqrt n)$. These points are $a$-separated. Use $Q=P_0$, the joint distribution when $\theta=0$.

For a single observation, the Kullback–Leibler divergence between $N(\theta,\sigma^2)$ and $N(0,\sigma^2)$ is $\theta^2/(2\sigma^2)$. Independence makes the divergence for $n$ observations $n\theta^2/(2\sigma^2)$. Averaging over the four selected parameters gives $$ \frac{1}{4}\sum_{j=0}^3\operatorname{KL}(P_{ja}\|P_0) =\frac{n a^2}{2\sigma^2}\frac{0^2+1^2+2^2+3^2}{4} =\frac{7na^2}{4\sigma^2} =\frac{7}{100}=0.07. $$ Here $na^2/\sigma^2=1/25$. Since $M=4$, the resulting decoding error bound is $$ P_e\geq1-\frac{0.07+\log2}{\log4}\approx 0.4495. $$ The metric risk is consequently at least $$ \frac{a}{2}(0.4495\ldots)\approx 0.2248a =\frac{0.4495\ldots}{10}\frac{\sigma}{\sqrt n} \approx 0.0450\frac{\sigma}{\sqrt n}. $$ This is a lower bound obtained from this particular four-point packing; a different packing or reference distribution may yield a stronger one.

Worked Example: Four Noisy Labels and the Metric Conversion

Let the parameter set be $\Theta=\{1,2,3,4\}$ with the discrete metric $d(j,k)=1$ for $j\neq k$ and $d(j,j)=0$. Let the observation $Z$ also take values in this set. Given $J=j$, suppose $P_j(Z=j)=1/2$, and each of the three other labels has probability $1/6$.

With $J$ uniform, each output label has marginal probability $1/4$: for any fixed $z$, the four conditional probabilities sum to $1/2+3(1/6)=1$, and the marginal is therefore $1/4$. Thus $H(Z)=\log4$. The conditional entropy is $$ H(Z\mid J)= -\frac12\log\frac12-3\left(\frac16\log\frac16\right) =\frac12\log2+\frac12\log6. $$ It follows that $$ I(J;Z)=\log4-\frac12\log2-\frac12\log6 \approx 0.143841. $$ Fano’s inequality gives $$ P_e\geq1-\frac{0.143841+\log2}{\log4}\approx0.3962. $$ For an estimator whose output is one of the four labels, the metric loss is exactly one when the label is wrong and zero when it is correct. Its average risk is therefore its decoding error probability, so its worst-case risk is at least $0.3962$. The general metric theorem alone gives the weaker bound $(1/2)(0.3962)\approx0.1981$, since its geometric conversion uses $\delta/2$. This example shows why the general conversion can be conservative when the loss has a more direct relationship to classification error.

How to Use the Bound and What Can Go Wrong

The packing determines the geometric difficulty of the estimation problem: its separation $\delta$ sets the scale of the risk bound, while its size $M$ supplies the identification entropy $\log M$. The data distributions determine how much information is available to identify the packed point. The bound is informative when the average divergence, or another upper bound on $I(J;Z)$, is substantially smaller than $\log M$. A large packing is not enough by itself: if the distributions are easy to distinguish, the Fano lower bound may be zero or nearly zero.

A common mistake is to treat a decoding error as though it automatically implies metric loss of at least $\delta$. The estimate is not required to equal a packed point; it could lie between two of them. The triangle inequality only guarantees loss at least $\delta/2$: if it were closer than $\delta/2$ to the true point, no other point at distance at least $\delta$ could be at least as close. Use $\delta/2$ for general metric loss unless the structure of the estimator or loss proves a stronger conversion.

Another pitfall is to use an average divergence without specifying its reference distribution or its direction. The identity above controls $I(J;Z)$ by the average $\operatorname{KL}(P_j\|Q)$, not by an arbitrarily reversed divergence. Check that the chosen divergences are finite and that the same $Q$ is used for every packed point. Finally, a negative right-hand side from Fano’s expression is not a negative risk bound; it means this particular information bound gives no positive conclusion.

Select a packing.
Choose $M\geq2$ parameters whose pairwise metric distances are at least $\delta$.

Bound information.
Use Fano’s inequality and, when useful, upper-bound $I(J;Z)$ by average Kullback–Leibler divergence to a reference distribution.

Convert to risk.
Decode the estimate by its nearest packed point; a decoding error forces metric loss of at least $\delta/2$.

Key takeaway: A $\delta$-separated packing with many points creates a finite identification problem. If the observations do not contain enough information to identify the packed parameter, then every estimator must incur metric risk of at least $\delta/2$ times the corresponding Fano error lower bound.

Check Your Understanding

Answer each question using the definitions and arguments above.

Why does a decoding error imply metric loss at least $\delta/2$, rather than necessarily at least $\delta$?
In the metric Fano theorem, what is the role of choosing $J$ uniformly over the packed indices?
State the conditions under which an average divergence to a reference distribution bounds $I(J;Z)$.
For the Gaussian example, which part of the calculation changes if the spacing $a$ is doubled while $n$ and $\sigma$ stay fixed?
Why can Fano’s inequality give no positive lower bound even when the parameter set contains a large separated packing?

Fano’s Method for Metric Estimation

What You'll Learn