The Wikipedia article on Fano's Inequality presents a generalization as follows:

Let $\mathbf{F}$ be a class of probability densities with a subclass of $r+1$ densities denoted $f_{\theta^{(i)}}$ for $i = 1,\ldots, r+1$ such that for $i\neq j$, \begin{eqnarray} \left|\left|f_{\theta^{(i)}} - f_{\theta^{(j)}}\right|\right|_1 &\geq& \alpha\\ D_{\text{KL}}\left(f_{\theta^{(i)}}\left|\right| f_{\theta^{(j)}}\right) &\geq& \beta. \end{eqnarray}

Then the bound holds, \begin{eqnarray} \sup_{f\in\mathbf{F}} \mathbb{E}\left[\left|\left|f_n - f\right|\right|_1\right] \geq\frac{\alpha}{2} \left(1 - \frac{n\beta - \log 2}{\log r}\right). \end{eqnarray}

Here, $f_n$ denotes a density estimator based on $n$ samples from the distribution $f$. I like this bound because it incorporates the sample size. Sadly, the Wikipedia article does not elaborate much on this generalized form of the inequality and all of the references seem to be either unavailable or in French (a language I don't read).

So, my first question is if anyone can direct me to a resource that discusses this construction in greater detail, particularly those showing a proof of the construction.

Second, I happened across this resource at Berkeley (see Lemma 3) that gives a derivation of a similar bound. The main differences seem to be,

  1. that the maximum is taken over the subclass of densities rather than $\mathbf{F}$ itself, and
  2. that there is no dependency (or even mention of) a sample size $n$.

I like point 1. but don't like 2. So my second question is whether or not there exists a bound of the form, \begin{eqnarray} \max_{i\in\left\{1,\ldots,r+1\right\}} \mathbb{E}\left[f_n - f_{\theta^{(i)}}\right] \geq \frac{\alpha}{2}\left(1 - \frac{n\beta - \log 2}{\log r}\right) \end{eqnarray} Which has the two properties I liked.

  • $\begingroup$ Maybe you could try and work out yourself. $\endgroup$ – Suzu Hirose Dec 2 '14 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.