4
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Is there a corresponding result for finite alphabets? Let $d(P,Q)$ be the $\ell_1$ distance in finite alphabets. Pinsker's inequality states that $$d(P,Q)\leq \sqrt{2 \ln 2 D(P||Q)}$$ in this case. $\endgroup$ – kodlu Mar 6 '15 at 2:32
  • $\begingroup$ @kodlu, I am talking about chi-square distance and not total variation distance. In finite alphabet it is not very hard to show that $\chi^2(P||Q)\leq \frac{1}{Q_{min}}d(P,Q)\leq \frac{1}{Q_{min}}\sqrt{2\ln 2 D(P||Q)}$ where $Q_{min}:=\min_{x\in \mathcal{X}} Q(x)$. This bounds collapse for general alphabet. $\endgroup$ – SAmath Mar 6 '15 at 23:35
  • $\begingroup$ @SAmath, have you found an answer to this question after all? $\endgroup$ – odea Jul 28 '18 at 23:31
  • $\begingroup$ Sorry to resuscitate this question, but the definition of $\chi^2$ seems wrong to me -- namely, there is a $-1$ term missing. With this correction, the desired inequality holds due to the inequality $$\log x \leq x-1$$. $\endgroup$ – Clement C. Oct 21 '18 at 21:38
3
$\begingroup$

@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). $$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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 $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the question asked the bound the other way around, e.g., if there is some constant $c$ such that $\chi^2(P||Q) \leq c D(P||Q)$. This is also what I needed. $\endgroup$ – odea Nov 10 '18 at 9:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.