5
$\begingroup$

There are many well-known relationships between the KL divergence, chi-squared ($\chi^2$) divergence, and the Hellinger metric. In the paper "Assouad, Fano, and Le Cam" by Bin Yu, the author appears to use the following relationship (see Example 2, p. 433): $$ \text{KL}(f,g) \le \int \frac{(\sqrt{f}-\sqrt{g})^2}{f}\,dx. $$ This looks almost like the standard relationship $\text{KL}(f,g)\le \chi^2(f,g)$, but differs in the square roots taken in the numerator. I have not seen this general relationship previously.

My question is: Does this inequality hold for general densities $f,g$?

(Note: In the paper, this inequality is applied to special choices of $f$ and $g$, and so maybe the author only means it for these functions. It is not clear to me based on the writing.)

$\endgroup$
1

2 Answers 2

6
$\begingroup$

This inequality is false in general.

E.g., let $f$ and $g$ be pdf's on $[0,1]$ given by the formulas $f=1$ and $g=f+t\,1_{(0,1/2)}-t\,1_{(1/2.1)}$ for $t\in(0,1)$. Then the left- and right-hand sides of your inequality are, respectively, $\sim t^2/2$ and $\sim t^2/4$ as $t\downarrow0$, so that your inequality fails to hold.

Moreover, if here $t\uparrow1$, then the left- and right-hand sides of your inequality go, respectively, to $\infty$ and $1-1/\sqrt2$. So, your inequality will fail to hold even if any extra universal constant factor is inserted on its right-hand side.


Here is the graph of the ratio the left-hand side of your inequality to its right-hand side:

enter image description here


The reason for such counterexamples is that $\text{KL}(f,g)=\int f\ln\frac fg$ can be arbitrarily large if $g$ is allowed to take values much smaller than the corresponding values of $f$, whereas the right-hand side of your inequality will remain bounded if $f$ is (say) bounded away from $0$ on the set where $g>0$.

$\endgroup$
2
  • 1
    $\begingroup$ Tried to build on this nice counterexample by giving a counterexample that is piecewise constant and another which is smooth. I think this shows the inequality does not hold even under the conditions cited in Section 29.3 of the paper shared by the OP. $\endgroup$ Aug 10 at 18:35
  • 1
    $\begingroup$ @NawafBou-Rabee : Thank you for your comment. $\endgroup$ Aug 10 at 19:03
3
$\begingroup$

The inequality does not hold for even simple densities which fulfill the conditions given in Section 29.3 of the paper shared by the OP.


Here is a piecewise constant counterexample, $$ f(x) = \frac{3}{2} 1_{\{(0,1/2)\}}(x) + \frac{1}{2} 1_{\{ (1/2,1) \}}(x) $$ $$ g(x) = \frac{1}{2} 1_{\{(0,1/2)\}}(x) + \frac{3}{2} 1_{\{ (1/2,1) \}}(x) $$ These functions are (i) probabilities densities whose support is $(0,1)$; (ii) they are bounded from above/below; and (iii) piecewise constant. However, the KL divergence between the corresponding distributions is $$ \int_0^1 f(x) \log(f(x)/g(x)) dx = \log(3)/2 \ge 1/2 $$ whereas the claimed upper bound is $$ \int_0^1 \frac{(\sqrt{f(x)} - \sqrt{g(x)})^2}{f(x)} dx = \frac{(\sqrt{6}-\sqrt{2})^2}{3} \le 1/2 \;. $$


And, here is a smooth counterexample, $$ f \equiv 1 $$ $$ g(x) = 2 (1-x) $$ In this case, by direct integration, the KL divergence is $(2-4\sqrt{2})/3 > 1/4$ while the claimed upper bound is $2 - 4 \sqrt{2}/3<1/4$.


All this seems to point to a possible bug in Example 2 of the paper.

$\endgroup$

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.