On the equivalence between the Kullback-Leiber divergence and the $L^2$ distance.

1.2k Views Asked by At

There is a question very similar to this one here, matter of fact I was looking to see if this equivalence was true and I stumbled upon that question.

For the sake of completeness I quote the question:

Let $P$ and $Q$ be two probability measures with densities $p$ and $q$ with respect to the Lebesgue measure on [0,1] such that: $0<a\leq p(x)\leq b$, $0<a\leq q(x)\leq b$ $\forall x\in $[0,1] $a$,$b>0$ are constants. Show that the Kullback distance $K(P,Q)$ is equivalent to the squared $L^2$ distance between densities $p$ and $q$.

where I assume the Op is talking about the standard Kullback leiber divergence

$$K(P,Q):= \int_{- \infty}^{+\infty} p(x) \log \frac{p(x)}{q(x)} \, dx$$

that is not, in fact, a distance (it is missing the symmetry property). Nonetheless we want to show there are two constants $\alpha$ and $\beta$ such that $\alpha||p-q||_{L^2}^{2}\leq K(P,Q)\leq \beta ||p-q||_{L^2}^{2}$.

  • How does one show the lower bound?
  • I assume what the OP of the linked question is doing for the upper bound is that he is expanding $\log(q(x))$ at the point $p(x)$ resulting in

$$\int_{0}^{1} p(x) \log \frac{p(x)}{q(x)} \, dx \le \int_{0}^{1}-p(x) ( q(x) - p(x)) \frac{1}{p(x)} + \frac{1}{2 p(x)^2}( q(x) - p(x))^2 \, dx \le $$

$$\int_{0}^{1} ( q(x) - p(x)) \, dx + \frac{1}{2 a^2} \int_{0}^{1}(q(x) - p(x))^2 \, dx = \frac{1}{2 a^2} \int_{0}^{1}(q(x) - p(x))^2 \, dx $$

where we have been assuming continuity of $q(x)$. But the Op of the linked question obtains some extra constants before the $L^2$ norm so I am afraid my calculation are incorrect (as they often have been) could somebody point out my mistake?

1

There are 1 best solutions below

5
On BEST ANSWER

The lower bound is an application of the so called Csiszár-Kullback-Pinsker inequality. If you are interested in proving it, i would refer to the book "Entropy Methods for Diffusive Partial Differential Equations" written bei Ansgar Jüngel. In the appendix he gives a very nice instruction for a more general result. You can easily modify this proof to obtain your desired result. If you do not have access to this text you might find a proof using google and above keyword aswell.

Regarding your attempt: I am not sure if i understand your first estimate properly. Lets start with the taylor expansion you are talking about. Since both densities are positive we write: $$\log(q(x)) = \log \left( (q(x)-p(x))+p(x) \right) = \log \left( p(x)\left( \left( \frac{q(x)}{p(x)}-1 \right)+1 \right)\right) \\ = \log(p(x)) + \log \left( \left( \frac{q(x)}{p(x)}-1 \right)+1 \right). $$ Above equation reduces the problem to expanding the logarithm at $x_0 = 1$. This can be done as follows $$ \log(s) = 0+ 1(s-1) - \frac{(s-1)^2}{2} \int_{1}^{s}\frac {1}{t^2} \mathrm{d}t$$ which leads to $$ \log(s+1) = s - \frac{s^2}{2} \int_{1}^{s+1}\frac {1}{t^2} \mathrm{d}t.$$ We conclude \begin{align*} \int_{0}^{1} p(x) \log \frac{p(x)}{q(x)} \mathrm{d}x &= \int_{0}^{1} p(x) \log ({p(x)}) -p(x) \log({q(x)}) \mathrm{d}x \\ &= \int_{0}^{1} p(x) \log ({p(x)}) \mathrm{d}x - \int_0^1 p(x) \log(p(x)) +p(x) \log \left( \left( \frac{q(x)}{p(x)}-1 \right)+1 \right) \mathrm{d}x \\ &= \int_0^1 -p(x) \log \left( \left( \frac{q(x)}{p(x)}-1 \right)+1 \right) \mathrm{d}x \\ &= \int_0^1 -p(x) \left( \frac{q(x)}{p(x)}-1 \right)+ p(x) s^2 \int_1^{s+1} \frac{1}{t^2} \mathrm{d}t\mathrm{d}x \\ &= \int_0^1 -\left({q(x)}-{p(x)} \right)+ p(x) s^2 \frac{s}{s+1}\mathrm{d}x \\ &= \int_0^1 -\left({q(x)}-{p(x)} \right)+ \left(q(x)-p(x)\right)^2 \left( \frac{1}{p(x)} -\frac{1}{q(x)}\right) \mathrm{d}x \\ &= \int_0^1 \left(q(x)-p(x)\right)^2 \left( \frac{1}{p(x)} -\frac{1}{q(x)}\right) \mathrm{d}x \end{align*} abrreviating $s = \left( \frac{q(x)}{p(x)}-1 \right)$. So far we didnt use the bounds on $p$ and $q$ except for deducing their positivity. We finally estimate \begin{align*} \int_{0}^{1} p(x) \log \frac{p(x)}{q(x)} \mathrm{d}x &\le \int_0^1 \left(q(x)-p(x)\right)^2 \left( \frac{1}{p(x)} -\frac{1}{q(x)}\right) \mathrm{d}x \\ &\le \int_0^1 \left(q(x)-p(x)\right)^2 \left( \frac{1}{a} -\frac{1}{b}\right) \mathrm{d}x \\ &= \frac{b-a}{ab} \|p-q\|_{L^2}. \end{align*} We remark that the estimate for the logarithm is a pointwise estimate. This means in above calculation one doesnt need $q$ and $p$ to be continuous.

If you want to, you might aswell show more of you steps so we can compare our constants. Further it would be possible to see if your way is right or you made a mistake.

Remark: In the case $a>\frac{1}{2}$ above inequality is indeed stronger than the one given in your attempt for all $b \le \frac{2a^2}{2a-1}$. Further we can brutally estimate the above inequality to obtain the constant $\frac{1}{a}$ which is stronger than yours in the case $a \le \frac{1}{2}$. For the remaining case i am not sure which way to go.

Regarding the constants in the other OP's question i have no idea how he got these. However her the situation is clearer: the estimate with $\frac{b-a}{ab}$ is in every case stronger than the one given in the other post. So you might estimate above expression to get the one in his/her post.