An upper bound for chi-square divergence in terms of KL divergence for general alphabets

Question

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ defined over a general alphabet $\mathcal{X}$, if $P\ll Q$, then $$\chi ^2(P||Q):=\int_{\mathcal{X}}\Big(\frac{dP}{dQ}\Big)^2dQ$$ and $$D(P||Q):=\int_{\mathcal{X}}dP\log\frac{dP}{dQ}.$$

I am looking for an upper bound of $\chi^2(P||Q)$ in terms of $D(P||Q)$ which works wven if $\mathcal{X}$ is uncountable. What I need is a special case where $P=P_{XY}$ and $Q=P_X\times P_Y$, for two random variables with joint and product distributions are $P_{XY}$ and $P_X\times P_Y$, respectively. Noticing that in this case KL divergence is equal to the mutual information , I need an upper bound of chi-square divergence in terms of mutual information.

Answer 1

Your definition of $\chi^2$ divergence is missing a term; namely, $$ \chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2 = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1 $$ (see e.g. this Wikipedia article on $f$-divergences).

With this in hand, recall that by concavity of the logarithm, we have $$ \log x \leq x-1, \qquad \forall x >0 $$ (where $\log$ denotes the natural logarithm), and thus $$\begin{align} D(P\| Q) &= \int_{\mathcal{X}} dP\log\frac{dP}{dQ}\\ &\leq \int_{\mathcal{X}} dP\left(\frac{dP}{dQ} - 1\right) \\ &= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1 \end{align}$$ showing that the inequality holds: $$ D(P\| Q) \leq \chi^2(P\|Q)\,,\qquad \forall P\ll Q $$

Answer 2

@odea, one can see that $\chi^2(P||Q) \leq c D(P||Q)$ cannot hold in general by taking a two point space with $P = \{ 1 , 0\}$ and $Q = \{ q, 1-q \}$. Then $\chi^2(P ; Q) = \frac 1 q -1$ while $D(P||Q) = \log \frac 1 q$. Such a $c$ would need to satisfy $c \geq \frac{x-1}{\log x}$ for $x \to \infty$.

However, if one assumes that $c=\| \frac{dP}{dQ} \|_\infty < \infty$, one can follow the argument above with $\log x \geq \frac{x-1}{x}$. $$ c D(P||Q) \geq \|\frac{dP}{dQ}\|_\infty \int_{\mathcal{X}} dP \left(\frac{\frac{dP}{dQ} -1 }{\frac{dP}{dQ}} \right) \geq \chi^2(P;Q). $$