Does large mutual information (between observations and parameter) imply the existence of a good estimator?

Question

This question concerns the standard setting for applying Fano's inequality to derive minimax bounds for a parameter estimation problem.

The goal is to estimate a parameter described by a random variable $X$ taking values $x \in \mathcal{X}$, where the set of possible parameters has bounded size, $|\mathcal{X}| = M$. I get observations in the form of a random variable $Y$, and then output an estimator $\hat{X} = f(Y)$ such that $X \rightarrow Y \rightarrow \hat{X}$ is a Markov chain.

One can then use Fano's inequality to show how the best that a classifier can perform is bounded by the mutual information $I(Y:X)$ between the observations and the parameter, e.g. \begin{equation} P(\hat{X} \neq X) \geq 1 - \frac{ I(Y:X) + \log 2}{\log M}. \tag{1} \end{equation} In practice, Eq. (1) is useful for showing that a classifier is guaranteed to fail if the mutual information between observations $Y$ and parameter $X$ is upper bounded like $I(Y:X) \ll \log M$.

---

My question is, if $I(Y:X)$ can be lower bounded, does this imply the existence of an estimation scheme $f$ (with minimal assumptions) such that $P(\hat{X} \neq X)$ can be upper bounded? Otherwise what is a simple counterexample (again, with minimal assumptions)?

More informally, if Fano's inequality (and the data processing inequality therein) says "garbage in $\Rightarrow$ garbage out", is there some statement like "(not garbage) in $\Rightarrow$ some way to get (not garbage) out"?

Answer 1

Yes. For instance, the error of an optimal estimator (i.e. maximum a posteriori estimator) may be upper bounded in terms of $H(X|Y)$. If we let the random variable $\hat{X}$ describing our estimator take values according to \begin{equation} \hat{x}(y) = \arg\max_{x} \text{Pr}(X=x|Y=y), \tag{1} \end{equation} Then an example of such a bound is, \begin{equation} \phi^*(\text{Pr}(\hat{X} \neq X)) \leq H(X|Y), \end{equation} where $\phi^*$ is defined in (Feder, 1994) but is most importantly monotonic. For example, if $\text{Pr}(\hat{X} \neq X) \leq 1/2$ (e.g. in the case of binary random variables) this rearranges to

\begin{equation} \text{Pr}(\hat{X} \neq X) \leq \frac{1}{2}\left(H(X) - I(X:Y)\right), \end{equation} which recovers the expected $\text{Pr}(\hat{X} \neq X)=0$ when $I(Y:X) = H(X)$.