1 Entropy and KL divergence

While studying the derivation of minimax lower bounds in nonparametric statistics, I recently came across Fano’s method. The intrinsic connection between it and information theory is fascinating. This note intends to reorganize these concepts using the language of measure theory to facilitate a deeper understanding. For probability theory, while Durrett’s textbook [2] is widely recommended, my personal references of choice are [3] and [4].

Let’s start from the concept of entropy. Let the ambient probability measure space be $(E,ℰ,\mathbb{P})$. Suppose the real valued random variable $X$ has the density function $p(x)$, that is, ${\mathbb{P}}_X:=\mathbb{P}\circ X^{-1}$ is absolutely continuous with respect to the Lebesgue measure. The differential entropy is defined as

$H(X)=𝔼[-\log p(X)]=-{\displaystyle {\int }_{ℝ}}p(x)\log p(x)dx.$

It is the continuous analogue of the Shannon entropy for discrete random variables.

Consider two random variables $X$ and $Y$, and ${\mathbb{P}}_{(X,Y)}={\mathbb{P}}_X\otimes \nu$, where $\nu$ is the conditional distribution of $Y|X$, that is, $\nu$ is a transition probability satisfying $\mathbb{P}(Y\in A|X=x):=𝔼[1_{Y\in A}|X=x]=\nu (x,A)$, ${\mathbb{P}}_X$-a.s for each $x\in ℝ$ and $A\in ℬ(ℝ)$. Suppose $(X,Y)$ has density function $p(x,y)$. Then the density of $X$ is $p_X(x)={\int }_{ℝ}p(x,y)dy$, where $p_X(x):=0$ if the integral is infinite (on a set of zero Lebesgue measure). Note that $A:=\{x:p_X(x)=0\}$ has zero ${\mathbb{P}}_X$-measure since ${\mathbb{P}}_X(A)={\int }_A{p}_X(x)dx=0$. Using Fubini’s theorem, one can verify for any $A,B\in ℬ(ℝ)$ that

${\mathbb{P}}_{(X,Y)}(A\times B)={\displaystyle {\int }_{A\times B}}p(x,y)dxdy={\displaystyle {\int }_A}\left({\displaystyle {\int }_B}{\displaystyle \frac{p(x,y)}{p_X(x)}}{1}_{p_X(x)>0}dy\right)p_X(x)dx.$

Therefore, we can define

$\nu (x,B)=1_{p_X(x)>0}{\displaystyle {\int }_B}{\displaystyle \frac{p(x,y)}{p_X(x)}}dy+1_{p_X(x)=0}{\displaystyle {\int }_B}\varphi (y)dy,$

where $\varphi (y)$ is an arbitrary density function. This implies that $\nu (x,\cdot )\ll \lambda$ for ${\mathbb{P}}_X$-a.e. $x$ (where $\lambda$ denotes the Lebesgue measure). The density function of $Y|X$ is $p_{Y|X}(y|x)=\frac{p(x,y)}{p_X(x)}{1}_{p_X(x)>0}+\varphi (y)1_{p_X(x)=0}$, which is unique in the ${\mathbb{P}}_X$-a.e. sense. The conditional entropy is then defined as

$H(Y|X)$ $={𝔼}_{{\mathbb{P}}_X}[H(Y|X=\cdot )]={\displaystyle {\int }_{ℝ}}\left({\displaystyle {\int }_{ℝ}}-p_{Y|X}(y|x)\log p_{Y|X}(y|x)\mathrm{d}y\right)p_X(x)dx$

$={\displaystyle {\int }_{ℝ\times ℝ}}-\log p_{Y|X}(y|x){\mathbb{P}}_{(X,Y)}(\mathrm{d}(x,y))=𝔼[-\log p_{Y|X}(Y|X)],$

where $H(Y|X=\cdot ):={\int }_{ℝ}-p_{Y|X}(y|\cdot )\log p_{Y|X}(y|\cdot )\mathrm{d}y$ is a measurable function defined in the ${\mathbb{P}}_X$-a.e. sense. Note that $H(Y|X)$ does not depend on the value of $p_{Y|X}(y|x)$ on $p_X(x)=0$, hence is well-defined. It holds that

$H(Y|X)$ $={\displaystyle {\int }_{ℝ}}\left({\displaystyle {\int }_{ℝ}}-p(x,y)[\log p(x,y)-\log p_X(x)]\mathrm{d}y\right)dx$

$=H(X,Y)-H(X).$

This is a commonly used identity in the information theory.

Now we recall the Kullback-Leibler (KL) divergence of two probability measures ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$ on $(E,ℰ)$. It is defined as

(1)

If ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$ have densities $p_1(x)$ and $p_2(x)$ with respect to a common dominating measure (e.g., Lebesgue measure), then the KL divergence becomes

$D_{\mathrm{KL}}({\mathbb{P}}_1\parallel {\mathbb{P}}_2)={\displaystyle {\int }_{ℝ}}{p}_1(x)\log {\displaystyle \frac{p_1(x)}{p_2(x)}}\mathrm{d}x.$

This is the most commonly used form (although not fully rigorous) in data science and machine learning. There are many important properties of the KL divergence. Here I only list three of them:

1. Additivity for product distributions:

   $D_{\mathrm{KL}}({\mathbb{P}}_1\otimes {\mathbb{Q}}_1\parallel {\mathbb{P}}_2\otimes {\mathbb{Q}}_2)=D_{\mathrm{KL}}({\mathbb{P}}_1\parallel {\mathbb{P}}_2)+D_{\mathrm{KL}}({\mathbb{Q}}_1\parallel {\mathbb{Q}}_2);$

2. Joint convexity:

   $D_{\mathrm{KL}}(\lambda {\mathbb{P}}_1+(1-\lambda ){\mathbb{Q}}_1\parallel \lambda {\mathbb{P}}_2+(1-\lambda ){\mathbb{Q}}_2)\le \lambda D_{\mathrm{KL}}({\mathbb{P}}_1\parallel {\mathbb{P}}_2)+(1-\lambda )D_{\mathrm{KL}}({\mathbb{Q}}_1\parallel {\mathbb{Q}}_2)$

   for any $0\le \lambda \le 1$;

3. Non-negativity (Gibbs’ inequality):

   $D_{\mathrm{KL}}({\mathbb{P}}_1\parallel {\mathbb{P}}_2)\ge 0,\text{with equality iff }{\mathbb{P}}_1={\mathbb{P}}_2.$

Here I give a short proof for the non-negativity based on the definition (1). We only need to prove the case that ${\mathbb{P}}_1\ll {\mathbb{P}}_2$. Let $\frac{\mathrm{d}{\mathbb{P}}_1}{\mathrm{d}{\mathbb{P}}_2}(\omega )=f(\omega )$, where $f$ is ${\mathbb{P}}_2$-a.s. measurable. By noticing that $x\log x$ is a convex function, using Jensen’s inequality we obtain

${𝔼}_{{\mathbb{P}}_1}\left[\log {\displaystyle \frac{\mathrm{d}{\mathbb{P}}_1}{\mathrm{d}{\mathbb{P}}_2}}\right]$ $={\displaystyle {\int }_E}{\displaystyle \frac{\mathrm{d}{\mathbb{P}}_1}{\mathrm{d}{\mathbb{P}}_2}}\log {\displaystyle \frac{\mathrm{d}{\mathbb{P}}_1}{\mathrm{d}{\mathbb{P}}_2}}\mathrm{d}{\mathbb{P}}_2$

$={\displaystyle {\int }_E}f(\omega )\log f(\omega ){\mathbb{P}}_2(\mathrm{d}\omega )$

$={\displaystyle {\int }_{ℝ}}x\log x({\mathbb{P}}_2\circ f^{-1})(\mathrm{d}x)$

$\ge {\displaystyle {\int }_{ℝ}}x({\mathbb{P}}_2\circ f^{-1})(\mathrm{d}x)\cdot \log \left({\displaystyle {\int }_{ℝ}}x({\mathbb{P}}_2\circ f^{-1})(\mathrm{d}x)\right)$

$=0,$

since ${\int }_{ℝ}x({\mathbb{P}}_2\circ f^{-1})(\mathrm{d}x)={\int }_{E}f(\omega ){\mathbb{P}}_2(\mathrm{d}\omega )={\mathbb{P}}_1(E)=1$.

For any two random variables $X$ and $Y$, their mutual information is defined as

$I(X;Y)=D_{\mathrm{KL}}({\mathbb{P}}_{(X,Y)}\parallel {\mathbb{P}}_X\otimes {\mathbb{P}}_Y).$ (2)

Suppose $(X,Y)$ has the density function $p(x,y)$. Then the density function of ${\mathbb{P}}_X\otimes {\mathbb{P}}_Y$ is $p_X(x)p_Y(y)$. Using that $\frac{\mathrm{d}{\mathbb{P}}_1}{\mathrm{d}{\mathbb{P}}_2}=\frac{\mathrm{d}{\mathbb{P}}_1/\mathrm{d}\mu }{\mathrm{d}{\mathbb{P}}_2/\mathrm{d}\mu }$ where ${\mathbb{P}}_1,{\mathbb{P}}_2\ll \mu$, one can verify

$I(X;Y)=H(X)+H(Y)-H(X,Y)=H(Y)-H(Y|X).$

Using the non-negativity of the KL divergence, the above identify implies that $H(Y|X)\le H(Y)$, i.e., conditioning reduces the entropy.

2 Fano’s inequality

Now we consider the nonparametric estimation. Suppose we have a family of probability distributions $𝒫=\{{\mathbb{P}}_{\theta }:\theta \in \mathrm{\Theta }\}$ on a measurable space $(F,ℱ)$, and a Borel measurable space on a metric space $(\mathrm{\Theta },d)$ with $d(\cdot ,\cdot )$ being the metric. From a statistical perspective, the aim is to estimate a parameter $\theta \in \mathrm{\Theta }$ from a sample data $X$ by assuming $X\sim {\mathbb{P}}_{\theta }$ with a $\theta \in \mathrm{\Theta }$. The whole set of estimators is ${𝒮}_{\text{est}}=\{\widehat{\theta }:(\widehat{\theta }:F\to \mathrm{\Theta })\text{ is measurable}\}$, consisting of all measurable maps from the observation space $F$ to parameter space $\mathrm{\Theta }$. In order to quantify the estimation in the worst case, consider the minimax risk

$\Re (\mathrm{\Theta })=\underset{\widehat{\theta }\in {𝒮}_{\text{est}}}{inf}\underset{\theta \in \mathrm{\Theta }}{sup}{𝔼}_{{\mathbb{P}}_{\theta }}\left[d(\widehat{\theta }(\cdot ),\theta )\right],$ (3)

where ${sup}_{\theta \in \mathrm{\Theta }}{𝔼}_{{\mathbb{P}}_{\theta }}[d(\widehat{\theta }(\cdot ),\theta )]$ is the worst-case risk given an estimator $\widehat{\theta }$. In particular, the definition of the minimax risk does not require an underlying random variable $X$. Nevertheless, in statistical inference one typically starts from sample data $X$ and then constructs an estimator $\widehat{\theta }(X)$.

Fano’s inequality is a fundamental tool in information theory and statistical minimax lower bounds. It provides a way to quantify the intrinsic difficulty of an estimation or decision problem by reducing it to a multi-class hypothesis testing problem. The core intuition is:

If the estimation problem is essentially a hard classification task (among $M$ possible distributions), and the available data does not provide enough information to reliably identify the true model, then any estimator will necessarily make large errors.

If we can construct a finite collection of well-separated parameters $\{{\theta }_1,\mathrm{\dots },{\theta }_M\}$, such that their corresponding distributions ${\mathbb{P}}_{{\theta }_1},\mathrm{\dots },{\mathbb{P}}_{{\theta }_M}$ are hard to distinguish (e.g., their KL divergences are small), then any estimator $\widehat{\theta }$ must incur large error.

The following version of Fano’s inequality is presented in a pure probabilistic manner, which is slightly different from the standard forms in the literature. It is adapted from the one presented in [1] with minor modifications.

Theorem 1 (Fano’s inequality).

Let $(E,ℰ,\mathbb{P})$ be a probability measure space such that $X:(E,ℰ)\to (F,ℱ)$ is an $F$-valued random variable and $J:E\to \{1,2,\mathrm{\dots },M\}$ is uniformly distributed with $M\ge 2$. Then for any measurable map $\psi :F\to \{1,2,\mathrm{\dots },M\}$, it holds

$\mathbb{P}\left(\psi (X)\ne J\right)\ge 1-{\displaystyle \frac{I(X;J)+\log 2}{\log M}}.$ (4)

Since $I(X;J)$ measures how much information the data $X$ carries about the hidden index $J$ (an interesting property is: $I(J;X)=I(X;J)\le H(J)$ with equality if and only if $J$ is determined by $X$), if $X$ is not sufficiently informative to distinguish among the $M$ hypotheses, then $I(X;J)$ is small. In this case, the lower bound in Fano’s inequality is larger, implying that any test $\psi (X)$ must fail to identify the true index $J$ with high probability.

3 Fano’s method for minimax lower bounds

Let’s come back to the nonparametric estimation. The basic settings are:

• A metric space $(\mathrm{\Theta },d)$ which leads to a Borel measurable space;

• A family of probability measures $𝒫=\{{\mathbb{P}}_{\theta }:\theta \in \mathrm{\Theta }\}$ on a measurable space $(F,ℱ)$;

• A set of estimators ${𝒮}_{\text{est}}=\{\widehat{\theta }:(\widehat{\theta }:F\to \mathrm{\Theta })\text{ is measurable}\}$.

From a pure theoretical perspective, an $F$-valued random variable $X$ is not needed. However, to establish Fano’s method, we will introduce such an $X$, and let $F$ to be a Polish space to ensure the existence of regular conditional distribution of $X$ knowing another random variable.

Theorem 2 (Fano’s method).

Suppose there are $M$ parameters ${\theta }_1,\mathrm{\dots },{\theta }_M\in \mathrm{\Theta }$ satisfying that:

• $d({\theta }_i,{\theta }_j)\ge 2\delta >0$ for all $i\ne j$;

• the average pairwise KL divergence satisfies

  ${\displaystyle \frac{1}{M^2}}{\displaystyle \sum _{i\ne j}}{D}_{\mathrm{KL}}({\mathbb{P}}_{{\theta }_i}\parallel {\mathbb{P}}_{{\theta }_j})\le \beta .$

Then it holds

$\underset{\widehat{\theta }\in {𝒮}_{\mathrm{est}}}{inf}\underset{1\le i\le M}{\max }{\mathbb{P}}_{{\theta }_i}\left(d(\widehat{\theta },{\theta }_i)\ge \delta \right)\ge 1-{\displaystyle \frac{\beta +\log 2}{\log M}}.$ (5)

Proof.

To apply Fano’s inequality, we introduce an ambient space $(E,ℰ,\mathbb{P})$ that ensures a uniformly distributed map $J:E\to \{1,2,\mathrm{\dots },M\}$ and a measurable map $\tilde{X}:E\to F$ satisfying $\tilde{X}|J=j\sim {\mathbb{P}}_{{\theta }_j}$. Then the distribution of $\tilde{X}$ is

${\mathbb{P}}_{\tilde{X}}(A)=𝔼[1_{\tilde{X}\in A}]=𝔼[𝔼[1_{\tilde{X}\in A}|J]]={\displaystyle \sum _{i=1}^M}𝔼[1_{\tilde{X}\in A}|J=j]\mathbb{P}(J=j)={\displaystyle \frac{1}{M}}{\displaystyle \sum _{j=1}^M}{\mathbb{P}}_{{\theta }_j}(A)$

for any $A\in ℱ$. This implies that ${\mathbb{P}}_{\tilde{X}}=\frac{1}{M}{\sum }_{j=1}^M{\mathbb{P}}_{{\theta }_j}$. Now we calculate $I(\tilde{X};J)$. It is easy to verify that ${\mathbb{P}}_{(\tilde{X},J)}\ll {\mathbb{P}}_{\tilde{X}}\otimes {\mathbb{P}}_J$. Let $f(x,j)=\frac{\mathrm{d}{\mathbb{P}}_{(\tilde{X},J)}}{\mathrm{d}({\mathbb{P}}_{\tilde{X}}\otimes {\mathbb{P}}_J)}(x,j)$. We have

$I(\tilde{X};J)$ $=D_{\mathrm{KL}}\left({\mathbb{P}}_{(\tilde{X},J)}\parallel {\mathbb{P}}_{\tilde{X}}\otimes {\mathbb{P}}_J\right)={𝔼}_{{\mathbb{P}}_{(\tilde{X},J)}}\left[\log f\right]$

$=𝔼\left[𝔼[\log f(\tilde{X},J)|J]\right]={\displaystyle \frac{1}{M}}{\displaystyle \sum _{j=1}^M}{𝔼}_{{\mathbb{P}}_{{\theta }_j}}\left[\log f(\cdot ,j)\right].$

By noticing that

${\displaystyle \frac{{\mathbb{P}}_{{\theta }_j}(A)}{M}}={\mathbb{P}}_{(\tilde{X},J)}(A\times \{j\})={\displaystyle {\int }_{A\times \{j\}}}f(x,j)({\mathbb{P}}_{\tilde{X}}\otimes {\mathbb{P}}_J)(\mathrm{d}(x,j))={\displaystyle \frac{1}{M}}{\displaystyle {\int }_A}f(x,j){\mathbb{P}}_{\tilde{X}}(\mathrm{d}x),$

for any $A\in ℱ$ and $j\in \{1,\mathrm{\dots },M\}$, it holds ${\mathbb{P}}_{{\theta }_j}(A)={\int }_{A}f(x,j){\mathbb{P}}_{\tilde{X}}(\mathrm{d}x)$, implying $\frac{\mathrm{d}{\mathbb{P}}_{{\theta }_j}}{\mathrm{d}{\mathbb{P}}_{\tilde{X}}}=f(\cdot ,j)$. Thus,

$I(\tilde{X};J)={\displaystyle \frac{1}{M}}{\displaystyle \sum _{j=1}^M}{𝔼}_{{\mathbb{P}}_{{\theta }_j}}\left[\log {\displaystyle \frac{\mathrm{d}{\mathbb{P}}_{{\theta }_j}}{\mathrm{d}{\mathbb{P}}_{\tilde{X}}}}\right]={\displaystyle \frac{1}{M}}{\displaystyle \sum _{j=1}^M}{D}_{\mathrm{KL}}({\mathbb{P}}_{{\theta }_j}\parallel {\mathbb{P}}_{\tilde{X}}).$

Using the convexity of KL divergence, we have

$D_{\mathrm{KL}}({\mathbb{P}}_{{\theta }_j}\parallel {\mathbb{P}}_{\tilde{X}})=D_{\mathrm{KL}}\left({\displaystyle \sum _{i=1}^M}{\displaystyle \frac{1}{M}}{\mathbb{P}}_{{\theta }_j}\parallel {\displaystyle \sum _{i=1}^M}{\displaystyle \frac{1}{M}}{\mathbb{P}}_{{\theta }_i}\right)\le {\displaystyle \frac{1}{M}}{\displaystyle \sum _{i=1}^M}{D}_{\mathrm{KL}}({\mathbb{P}}_{{\theta }_j}\parallel {\mathbb{P}}_{{\theta }_i}).$

Combining the above relations obtains

$I(\tilde{X};J)\le {\displaystyle \frac{1}{M^2}}{\displaystyle \sum _{i\ne j}}{D}_{\mathrm{KL}}({\mathbb{P}}_{{\theta }_i}\parallel {\mathbb{P}}_{{\theta }_j})\le \beta .$

Define the map $\psi :F\to \{1,2,\mathrm{\dots },M\}$ as $\psi (x)={argmin}_{1\le i\le M}d(\widehat{\theta }(x),{\theta }_i)$ (take the smallest index if there are multiple smallest ${\theta }_i$), which is measurable since $d(\cdot ,{\theta }_i)$ is Borel measurable on $\mathrm{\Theta }$. Then for any $1\le j\le M$ it holds

$d({\theta }_{\psi (x)},{\theta }_j)\le d(\widehat{\theta }(x),{\theta }_j)+d(\widehat{\theta }(x),{\theta }_{\psi (x)})\le 2d(\widehat{\theta }(x),{\theta }_j).$

Since $d({\theta }_{\psi (x)},{\theta }_j)\ge 2\delta$ when $\psi (x)\ne j$, we have

$\{\psi \ne j\}\subset \{d(\widehat{\theta },{\theta }_j)\ge \delta \}⟹{\mathbb{P}}_{{\theta }_j}\left(d(\widehat{\theta },{\theta }_j)\ge \delta \right)\ge {\mathbb{P}}_{{\theta }_j}\left(\psi \ne j\right).$

For this $\tilde{X}$, we have

$\mathbb{P}(\psi (\tilde{X})\ne J)=𝔼[𝔼[1_{\psi (\tilde{X})\ne J}|J]]={\displaystyle \frac{1}{M}}{\displaystyle \sum _{j=1}^M}{\mathbb{P}}_{{\theta }_j}(\psi \ne j).$

The above two relations lead to

$\mathbb{P}(\psi (\tilde{X})\ne J)\le {\displaystyle \frac{1}{M}}{\displaystyle \sum _{j=1}^M}{\mathbb{P}}_{{\theta }_j}\left(d(\widehat{\theta },{\theta }_j)\ge \delta \right)\le \underset{1\le i\le M}{\max }{\mathbb{P}}_{{\theta }_i}\left(d(\widehat{\theta },{\theta }_i)\ge \delta \right).$

Using Fano’s inequality, we obtain

$\underset{1\le i\le M}{\max }{\mathbb{P}}_{{\theta }_i}\left(d(\widehat{\theta },{\theta }_i)\ge \delta \right)\ge 1-{\displaystyle \frac{I(\tilde{X};J)+\log 2}{\log M}}\ge 1-{\displaystyle \frac{\beta +\log 2}{\log M}}.$

Taking infimum for $\widehat{\theta }$ gives the desired lower bound. ∎

Using the relation ${𝔼}_{{\mathbb{P}}_{\theta }}\left[d(\widehat{\theta },\theta )\right]\ge \delta {\mathbb{P}}_{\theta }\left(d(\widehat{\theta },\theta )\ge \delta \right)$, we have

$\underset{\theta \in \mathrm{\Theta }}{sup}{𝔼}_{{\mathbb{P}}_{\theta }}\left[d(\widehat{\theta },\theta )\right]\ge \underset{1\le i\le M}{\max }\delta {\mathbb{P}}_{{\theta }_i}\left(d(\widehat{\theta },{\theta }_i)\ge \delta \right).$

Then the Fano’s method gives

$\Re (\mathrm{\Theta })\ge \delta \left(1-{\displaystyle \frac{\beta +\log 2}{\log M}}\right).$

In [5, §2.6], there are several other variants of Fano’s method, all sharing the same core intuition as the version presented here. A systematic application of Fano’s method as well as other methods to concrete statistical inference problems can also be found in this book.