Information Theory — A Guided Tour of Modern Statistics

Notes / Function Spaces

6.4 Information Theory

To prove lower bounds, we turn to information theory, which lets us reduce estimation to hypothesis testing and gives us two main tools for the job: Le Cam’s method and Fano’s inequality.

6.4.1 Fundamentals

Entropy: We begin with a central concept in information theory: the entropy. Let \(P\) be a distribution on a finite (or countable) set \(\mathcal {X}\), and let \(p\) denote the probability mass function associated with \(P\). That is, if \(X\) is a random variable distributed according to \(P\), then \(P(X = x) = p(x)\). The entropy of \(X\) (or of \(P\)) is defined as \begin{equation} H(X) := -\sum _{x} p(x) \log p(x). \end{equation} Because \(p(x) \leq 1\) for all \(x\), it is clear that this quantity is positive. We will show later that if \(\mathcal {X}\) is finite, the maximum entropy distribution on \(\mathcal {X}\) is the uniform distribution, setting \(p(x) = 1/|\mathcal {X}|\) for all \(x\), which has entropy \(\log (|\mathcal {X}|)\).

Mutual information: The mutual information \(I(X;Y)\) between \(X\) and \(Y\) is the KL-divergence between their joint distribution and their products (marginal) distributions. More mathematically, \begin{equation} I(X;Y) := \sum _{x,y} p(x,y) \log \frac {p(x,y)}{p(x)p(y)}. \end{equation} We can rewrite this in several ways. First, using Bayes’ rule, we have \(p(x,y)/p(y) = p(x \mid y)\), so \begin{align*} I(X;Y) &= \sum _{x,y} p(y) p(x \mid y) \log \frac {p(x \mid y)}{p(x)} \\ &= -\sum _{x} \sum _{y} p(y) p(x \mid y) \log p(x) + \sum _{y} p(y) \sum _{x} p(x \mid y) \log p(x \mid y) \\ &= H(X) - H(X \mid Y). \end{align*}

Similarly, we have \(I(X;Y) = H(Y) - H(Y \mid X)\), so mutual information can be thought of as the amount of entropy removed (on average) in \(X\) by observing \(Y\). We may also think of mutual information as measuring the similarity between the joint distribution of \(X\) and \(Y\) and their distribution when they are treated as independent \begin{equation*} I(X;Y) = D_{\mathrm {KL}}\left (P_{XY} \,\|\, P_X \times P_Y\right ) \geq 0. \end{equation*} Moreover, we have \(I(X;Y) > 0\) unless \(X\) and \(Y\) are independent.

Entropies of continuous random variables For continuous random variables, we may define an analogue of the entropy known as differential entropy, which for a random variable \(X\) with density \(p\) is defined by \begin{equation} h(X) := -\int p(x) \log p(x) \, dx. \end{equation}

Proof. Without loss of generality, we assume that \(X\) has mean \(0\). Let \(P\) be the distribution of \(X\) with density \(p\), and let \(Q\) be multivariate normal with mean \(0\) and covariance \(\Sigma \); let \(Z\) be this random variable. Then \begin{align*} D_{\mathrm {KL}}(P \| Q) = \int p(x) \log \frac {p(x)}{q(x)} \, dx &= -h(X) + \int p(x) \left [ \frac {n}{2} \log (2\pi ) - \frac {1}{2} x^\top \Sigma ^{-1} x \right ] dx \\ &= -h(X) + h(Z), \end{align*}

because \(Z\) has the same covariance as \(X\). As \(0 \leq D_{\mathrm {KL}}(P \| Q)\), we have \(h(Z) \geq h(X)\) as desired. □

6.4.2 Data Processing Inequalities

A standard problem in information theory (and statistical inference) is to understand the degradation of a signal after it is passed through some noisy channel (or observation process). The simplest of such results, which we will use frequently, is that we can only lose information by adding noise. In particular, assume we have the Markov chain \begin{equation*} X \to Y \to Z. \end{equation*} Then we obtain the classical data processing inequality.

Proof. We expand the mutual information \(I(X;Y,Z)\) in two ways: \begin{align*} I(X;Y,Z) &= I(X;Z) + I(X;Y \mid Z) \\ &= I(X;Y) + \underbrace {I(X;Z \mid Y)}_{=0}, \end{align*}

where we note that the final equality follows because \(X\) is independent of \(Z\) given \(Y\): \begin{equation*} I(X;Z \mid Y) = H(X \mid Y) - H(X \mid Y, Z) = H(X \mid Y) - H(X \mid Y) = 0. \end{equation*} Since \(I(X;Y \mid Z) \geq 0\), this gives the result. □

There are related data processing inequalities for the KL-divergence—which we generalize in the next section—as well. In this case, we may consider a simple Markov chain \(X \to Z\). If we let \(P_1\) and \(P_2\) be distributions on \(X\) and \(Q_1\) and \(Q_2\) be the induced distributions on \(Z\), that is, \(Q_i(A) = \int \mathbb {P}(Z \in A \mid x) \, dP_i(x)\), then we have \begin{equation*} D_{\mathrm {KL}}(Q_1 \| Q_2) \leq D_{\mathrm {KL}}(P_1 \| P_2), \end{equation*} the basic KL-divergence data processing inequality. A consequence of this is that, for any function \(f\) and random variables \(X\) and \(Y\) on the same space, we have \begin{equation*} D_{\mathrm {KL}}(f(X) \| f(Y)) \leq D_{\mathrm {KL}}(X \| Y). \end{equation*}

6.4.3 Minimax Lower Bound

In statistical decision theory, we have a class of distributions \(\mathcal {P}\) and a parameter/function of distributions \(\theta : \mathcal {P} \to \Theta \). If this is a one to one mapping, we write \(\mathcal {P} = \{\mathbb {P}_\theta : \theta \in \Theta \}\). Then we have statistical estimators, which are mappings \(\widehat {\theta } : \mathcal {X} \to \Theta \). Suppose there is a semimetric \(\rho (\theta , \theta ') : \Theta \times \Theta \to \mathbb {R}\), such as \begin{equation*} \rho (\theta , \theta ') = \|\theta - \theta '\|_2, \qquad \rho (f, f') = \|f - f'\|_{L^2}. \end{equation*} If \(\Phi : [0, \infty ) \to [0, \infty )\) is increasing, the risk is \begin{equation*} R(\widehat {\theta }; \theta (P)) = \mathbb {E}_{X \sim P}[\Phi (\rho (\widehat {\theta }(X); \theta (P)))]. \end{equation*} In this framework, the loss function is \(\ell = \Phi \circ \rho \).

The inf and the sup mean that we are taking the best estimator for the worst model.

(a): If \(R(\widehat {\theta })\) achieves \(\mathcal {M}_n\), it is good enough.
(b): If \(R(\widehat {\theta }) \gg \mathcal {M}_n\), we should either find a better estimator or a sharper lower bound.

The idea is to find a testing problem easier than the estimation problem. A lower bound for the testing problem will imply a lower bound for estimation.

Step 1: Construct a \(2\delta \)-separated set of \(\Theta \) in the \(\rho \)-metric. So we require \(\rho (\theta ^i, \theta ^j) \geq 2\delta \) for all \(i \neq j\). This is the same as a packing, except we allow \(\geq \) instead of \(>\). If our separated set is \(\{\theta ^1, \theta ^2, \ldots , \theta ^M\}\), we get \(\{\mathbb {P}_{\theta ^1}, \mathbb {P}_{\theta ^2}, \ldots , \mathbb {P}_{\theta ^M}\}\).

Step 2: Sample \((J, Z) \in [M] \times \mathcal {X}\). The joint distribution is \begin{equation*} \begin {cases} J \sim \mathrm {Unif}(\{1, 2, \ldots , M\}) \\ Z \mid J = j \sim \mathbb {P}_{\theta ^j}. \end {cases} \end{equation*}

Step 3: Let \(\mathbb {Q}\) be the joint distribution of \((J, Z)\). Then the marginal distribution of \(Z\) is \begin{equation*} \overline {\mathbb {Q}} = \frac {1}{M} \sum _{j=1}^{M} \mathbb {P}_{\theta ^j}. \end{equation*} Our testing problem is that we want to find a \(\psi : \mathcal {X} \to [M]\) such that \(\mathbb {Q}(\psi (Z) \neq J)\) is small. If \(M = 2\), this is standard binary hypothesis testing. The testing error is \begin{equation*} \mathbb {Q}(\psi (Z) \neq J) = \frac {1}{2} \big [ \underbrace {\mathbb {P}_{\theta ^1}(\psi (Z) \neq 1)}_{\text {Type I error}} + \underbrace {\mathbb {P}_{\theta ^2}(\psi (Z) \neq 2)}_{\text {Type II error}} \big ]. \end{equation*} This is different from the traditional hypothesis testing setup in that instead of fixing the Type I error and minimizing the Type II error, we want to minimize the average of these errors.

This works for all \(\delta > 0\), so we can pick the \(\delta \) which gives the best lower bound. In general, \(\Phi (\delta )\) is increasing with \(\delta \), but the testing error \(\inf _\psi \mathbb {Q}(\psi (Z) \neq J)\) is decreasing with \(\delta \). We can choose \(\delta = \delta _n\) such that \(\inf _\psi \mathbb {Q}(\psi (Z) \neq J) = \frac {1}{2}\); any constant would work here. Then the minimax lower bound will be \begin{equation*} \mathcal {M}_n \geq \frac {1}{2} \Phi (\delta _n). \end{equation*}

Proof. Fix \(P\) and \(\widehat {\theta }\). By Markov’s inequality, \begin{align*} \mathbb {E}[\Phi (\rho (\widehat {\theta }, \theta ))] &\geq \Phi (\delta ) \mathbb {P}(\Phi (\rho (\widehat {\theta }, \theta )) \geq \Phi (\delta )) \\ &= \Phi (\delta ) \mathbb {P}(\rho (\widehat {\theta }, \theta ) \geq \delta ). \end{align*}

We now want to relate this probability with the testing error. We have \begin{align*} \sup _{P \in \mathcal {P}} \mathbb {P}(\rho (\widehat {\theta }, \theta ) \geq \delta ) &\geq \sup _{\theta \in \{\theta ^1, \ldots , \theta ^M\}} \mathbb {P}_\theta (\rho (\widehat {\theta }, \theta ) \geq \delta ) \\ &\geq \frac {1}{M} \sum _{j=1}^{M} \mathbb {P}_{\theta ^j}(\rho (\widehat {\theta }, \theta ^j) \geq \delta ) \\ &= \mathbb {Q}(\rho (\widehat {\theta }, \theta ^J) \geq \delta ). \end{align*}

Define a test \(\psi \) via \(\widehat {\theta }\): Let \begin{equation*} \psi (z) = \arg \min _{L \in [M]} \rho (\widehat {\theta }(Z), \theta ^L). \end{equation*} This gives the \(\theta ^j\) which is the closest to our estimate \(\widehat {\theta }(Z)\). With this definition, \begin{equation*} \{\psi (Z) \neq J\} \subseteq \{\rho (\widehat {\theta }(Z), \theta ^J) \geq \delta \}. \end{equation*} This means we can lower bound the above \(\mathbb {Q}\) probability: \begin{equation*} \inf _{\widehat {\theta }} \mathbb {Q}(\rho (\widehat {\theta }(Z), \theta ^J) \geq \delta ) \geq \inf _{\psi } \mathbb {Q}(\psi (Z) \neq J). \end{equation*} □

Some Divergence Measures Recall the definition of the total variation distance, the KL divergence, and the Hellinger distance \begin{align*} \|\mathbb {P} - \mathbb {Q}\|_{\mathrm {TV}} &= \frac {1}{2} \int _{\mathcal {X}} |p(x) - q(x)| \, dx, \\ D(\mathbb {P} \| \mathbb {Q}) &= \int _{\mathcal {X}} p(x) \log \frac {p(x)}{q(x)} \, dx, \\ \mathbb {H}^2(\mathbb {P} \| \mathbb {Q}) &= \int _{\mathcal {X}} \left ( \sqrt {p(x)} - \sqrt {q(x)} \right )^2 dx. \end{align*}

These have the following relationships: \begin{align*} \|\mathbb {P} - \mathbb {Q}\|_{\mathrm {TV}} &\leq \sqrt {\tfrac {1}{2} D(\mathbb {P} \| \mathbb {Q})}, \\ \|\mathbb {P} - \mathbb {Q}\|_{\mathrm {TV}} &\leq \sqrt {\mathbb {H}^2(\mathbb {P} \| \mathbb {Q})} \underbrace {\sqrt {1 - \frac {\mathbb {H}^2(\mathbb {P} \| \mathbb {Q})}{4}}}_{\leq 1}, \\ \mathbb {H}^2(\mathbb {P} \| \mathbb {Q}) &\leq \frac {1}{2} D(\mathbb {P} \| \mathbb {Q}). \end{align*}

Le Cam’s Two Points Method Take \(M = 2\). Then \(J \sim \mathrm {Unif}(\{0, 1\})\), and \(Z \mid J = j \sim \mathbb {P}_j\), and \(\overline {\mathbb {Q}} = \frac {1}{2}\mathbb {P}_0 + \frac {1}{2}\mathbb {P}_1\). We claim that \begin{equation*} \inf _\psi \mathbb {Q}(\psi (Z) \neq J) = \frac {1}{2}\left (1 - \|\mathbb {P}_0 - \mathbb {P}_1\|_{\mathrm {TV}}\right ). \end{equation*}

Proof. For any \(\psi \), we can find an \(A\) such that \begin{equation*} \psi (x) = \begin {cases} 1 & x \in A \\ 0 & x \in A^c. \end {cases} \end{equation*} Then \begin{align*} \mathbb {Q}(\psi (Z) = J) &= \frac {1}{2}\mathbb {P}_1(A) + \frac {1}{2}\mathbb {P}_0(A^c) \\ &= \frac {1}{2}(\mathbb {P}_1(A) - \mathbb {P}_0(A)) + \frac {1}{2}. \end{align*}

If we take the supremum over all \(\psi \), we get \begin{align*} \sup _\psi \mathbb {Q}(\psi (Z) = J) &= \sup _A \frac {1}{2}(\mathbb {P}_1(A) - \mathbb {P}_0(A)) + \frac {1}{2} \\ &= \frac {1}{2}\|\mathbb {P}_1 - \mathbb {P}_0\|_{\mathrm {TV}} + \frac {1}{2}. \end{align*}

The probability of the bad event is then \begin{equation*} \inf _\psi \mathbb {Q}(\psi (Z) \neq J) = \frac {1}{2} - \frac {1}{2}\|\mathbb {P}_1 - \mathbb {P}_0\|_{\mathrm {TV}}. \end{equation*} □

This gives the following theorem.

Example 6.40 (Gaussian Location Family, \(d=1\)). Our model is \(\mathcal {P} = \{\mathbb {P}_\theta = \mathsf {N}(\theta , \sigma ^2) : \theta \in \mathbb {R}\}\), where \(\sigma \) is known. We have the semimetric \(\rho (\theta ', \theta ) = |\theta ' - \theta |\) and \(\Phi (t) = t^2\). Our sample is \(X_{1:n} \sim \mathbb {P}_\theta ^n\). The true minimax risk is \(\mathcal {M}_n = \frac {\sigma ^2}{n}\). Here is a lower bound by Le Cam’s method:

Consider \(\mathbb {P}_{2\delta }\) and \(\mathbb {P}_0\), so \(\rho (2\delta , 0) \geq 2\delta \). Then \begin{equation*} \mathcal {M}_n(\theta (\mathcal {P}); |\theta - \theta '|^2) \geq \frac {\delta ^2}{2}\left (1 - \|\mathbb {P}_{2\delta }^n - \mathbb {P}_0^n\|_{\mathrm {TV}}\right ), \end{equation*} where the \(n\) only appears in the bound as the fact that the measures are product measures. We want to lower bound \(1 - \|\mathbb {P}_{2\delta }^n - \mathbb {P}_0^n\|_{\mathrm {TV}}\) by \(1/2\). We have by Pinsker’s inequality and the tensorization property of K-L divergence \begin{align*} \|\mathbb {P}_{2\delta }^n - \mathbb {P}_0^n\|_{\mathrm {TV}}^2 &\leq \frac {1}{2} D(\mathbb {P}_{2\delta }^n \| \mathbb {P}_0^n) \\ &= \frac {1}{2} n D(\mathbb {P}_{2\delta } \| \mathbb {P}_0) \\ &= \frac {1}{2} n \cdot \frac {(2\delta )^2}{2\sigma ^2} \\ &= \frac {n\delta ^2}{\sigma ^2}. \end{align*}

Now choose \(\frac {n\delta ^2}{\sigma ^2} = \frac {1}{2}\), so \(\delta _n^2 = \frac {\sigma ^2}{2n}\). Then \(\|\mathbb {P}_{2\delta _n}^n - \mathbb {P}_0^n\|_{\mathrm {TV}} \leq \frac {1}{2}\), and we get the minimax lower bound \begin{equation*} \mathcal {M}_n \geq \frac {\delta _n^2}{2} \cdot \frac {1}{2} = \frac {\sigma ^2}{16n}. \end{equation*} Up to constants, this is sharp.

Here is the problem with Le Cam’s method. If we take \(\theta \in \mathbb {R}^d\) with \(\mathbb {P}_\theta = \mathsf {N}(0, \sigma ^2 I_d)\) for \(d \geq 2\), then we will get the lower bound \begin{equation*} \mathcal {M}_n \geq \frac {\sigma ^2}{16n}, \end{equation*} even though the actual minimax risk is \(\mathcal {M}_n = \sigma ^2 \frac {d}{n}\).

Let \begin{equation*} \mathbb {Q} : \begin {cases} J \sim \mathrm {Unif}(\{1, 2, \ldots , M\}) \\ Z \mid J = j \sim \mathbb {P}_{\theta ^j}. \end {cases} \end{equation*}

The proof is in Section 15.4 and requires some ideas such as the entropy. This does not require any restriction on the \(\mathbb {P}_{\theta ^j}\). This lower bound gives us

When using this lower bound, we will find \(\delta _n\) such that \begin{equation*} 1 - \frac {I(Z;J) + \log 2}{\log M} \geq \frac {1}{2}. \end{equation*} Then we will get \begin{equation*} \mathcal {M}_n \geq \frac {1}{2} \Phi (\delta _n). \end{equation*} So we need to upper bound \(I(Z;J)\).

A simple upper bound is given by \begin{align*} I(J;Z) &= \frac {1}{M} \sum _{j=1}^{M} D\!\left ( \mathbb {P}_{\theta ^j} \,\Big \|\, \frac {1}{M} \sum _{\ell =1}^{M} \mathbb {P}_{\theta ^\ell } \right ) \\ &\leq \frac {1}{M^2} \sum _{j,\ell =1}^{M} D(\mathbb {P}_{\theta ^j} \| \mathbb {P}_{\theta ^\ell }) \\ &\leq \max _{j,\ell } D(\mathbb {P}_{\theta ^j} \| \mathbb {P}_{\theta ^\ell }). \end{align*}

Where we have used Jensen’s inequality to show that the K-L divergence is convex in the second argument.

Example 6.43 (Gaussian location family, \(d \geq 2\)). Our model is \(\mathcal {P} = \{\mathbb {P}_\theta = \mathsf {N}(0, \sigma ^2 I_d) : \theta \in \mathbb {R}^d\}\), where \(\sigma \) is known. Our semimetric is \(\rho (\theta ', \theta ) = \|\theta ' - \theta \|_2\) with \(\Phi (t) = t^2\). The true minimax risk is \begin{equation*} \mathcal {M}_n = \inf _{\widehat {\theta }} \sup _{\theta } \mathbb {E}[\|\widehat {\theta } - \theta \|_2^2] = \sigma ^2 \frac {d}{n}. \end{equation*} The lower bound by Fano’s method gives \begin{align*} \mathcal {M}_n &\geq \Phi (\delta ) \left ( 1 - \frac {I(Z;J) + \log 2}{\log M} \right ) \\ &\geq \Phi (\delta ) \left ( 1 - \frac {\max _{j,k} D(\mathbb {P}_{\theta ^j}^n \| \mathbb {P}_{\theta ^k}^n) + \log 2}{\log M} \right ). \end{align*}

Our goal is to find the largest \(\delta _n, M, \{\theta ^1, \ldots , \theta ^M\}\) such that

(a): \(\|\theta ^j - \theta ^k\|_2 \geq 2\delta _n\)
(b): \begin{equation*} \frac {\max _{j,k} D(\mathbb {P}_{\theta ^j}^n \| \mathbb {P}_{\theta ^k}^n) + \log 2}{\log M} \leq \frac {1}{2}. \end{equation*}

Here is our construction: Let \(\varepsilon _n = \sigma \sqrt {\frac {d}{n}}\) and \(\delta _n = \frac {1}{100} \varepsilon _n = \frac {1}{100} \sigma \sqrt {\frac {d}{n}}\). Let \(\{\theta ^1, \ldots , \theta ^M\}\) be a maximal \(2\delta _n\) packing of \(B(0, \varepsilon _n) = \{\theta \in \mathbb {R}^d : \|\theta \|_2 \leq \varepsilon _n\}\).

By a volume argument, we can get upper and lower bounds of \(M\): \begin{equation*} \log M \asymp d \log \left ( c \frac {\varepsilon _n}{\delta _n} \right ) \asymp c \cdot d. \end{equation*} To upper bound the K-L divergence on top, we have \begin{align*} \max _{j,k} D(\mathbb {P}_{\theta ^j}^n \| \mathbb {P}_{\theta ^k}^n) &= n \max _{j,k} D(\mathbb {P}_{\theta ^j} \| \mathbb {P}_{\theta ^k}) \\ &= n \max _{j,k} \frac {\|\theta ^j - \theta ^k\|_2^2}{2\sigma ^2} \\ &\leq \frac {n \varepsilon _n^2}{2\sigma ^2} \\ &= c \cdot d. \end{align*}

Our quantities only depend on the ratio between \(\varepsilon _n\) and \(\delta _n\), so we can adjust the constant in front of \(\delta _n\) to get the desired upper bound of \(\frac {1}{2}\).

We then get \begin{equation*} \mathcal {M}_n \geq \Phi (\delta _n) \frac {1}{2} = \frac {1}{2} \cdot \left ( \frac {1}{100} \right )^2 \sigma ^2 \frac {d}{n} = c \sigma ^2 \frac {d}{n}. \end{equation*}

The bound on \(I(J;Z)\) by the max of the K-L divergences is generally only good when we have a parametric problem. For nonparametric problems, we want to use a better bound.

To apply this bound, we have two steps:

1.: Choose \(\varepsilon _n > 0\) such that \begin{equation*} \varepsilon _n^2 \geq \log N_{\mathrm {KL}}(\varepsilon _n; \mathcal {P}). \end{equation*}
2.: Choose the largest \(\delta _n > 0\) such that \begin{equation*} \log M(\delta _n; \rho , \Omega ) \geq 4\varepsilon _n^2 + 2 \log 2. \end{equation*}