5
$\begingroup$

According to the Pinsker inequality, we have the following inequality: \begin{equation} \delta_{TV} (p, q)^2 \leq \frac{1}{2} D_{KL}(p,q), \end{equation} where $\delta_{TV} (\cdot, \cdot)$ and $D_{KL}(\cdot, \cdot)$ are total variation distance and Kullback–Leibler divergence, respectively.

On the other hand, the total variation distance is related to the $L_1$ norm by the identity: \begin{equation} \delta_{TV}(p, q) = \frac{1}{2} \int_{\mathcal{X}} |p(x)-q(x)| \, dx, \end{equation} and thus by using the Cauchy–Schwarz inequality we obtain that \begin{equation} \delta_{TV} (p, q)^2 \leq \frac{1}{4} \int_{\mathcal{X}} (p(x)-q(x))^2 \, dx. \end{equation} I denote the RHS by $L_2(p, q)$, i.e., $L_2(p, q) = \int_{\mathcal{X}} (p(x)-q(x))^2 \, dx$.

My question is: does there exist some (inequality) relation between the $D_{KL}(\cdot, \cdot)$ and $L_2(p, q)$?

$\endgroup$
0

4 Answers 4

6
$\begingroup$

Such inequality is impossible: consider $p(x)=1$, $q(x)=1/(2\sqrt{x})$, as probability densities on $(0,1)$. Then $D_{KL}(p\parallel q)$ is finite, while $\|p-q\|_2=\infty$, as $q\not\in L^2$.

The reverse direction is also impossible: take $p(x)=a e^{-ax}$, $q(x)=a^2e^{-a^2x}$ on $(0,\infty)$. Then $\|p-q\|_2\to0$, while $D_{KL}(q\parallel p)=1/a+\ln a -1\to\infty$, as $a\to0$.

$\endgroup$
6
$\begingroup$

To complement Iiro Ullin's answer, we have the following inequality in one direction:

Lemma (László Györfi). If $p$ and $q$ are probability densities both supported on a bounded interval $I$, then we have $$D_{\textrm{KL}}(p,q)\leq\frac{1}{\inf_{x\in I}q(x)}\|p-q\|_2^2$$

Proof. \begin{align} D_{\textrm{KL}}(p,q) &= \int_I p(x)\log\frac{p(x)}{q(x)}\mathrm{d}x \\ &\leq \int_I p(x)\left(\frac{p(x)}{q(x)}-1\right)\mathrm{d}x \\ &= \int_I \frac{\big(p(x)-q(x)\big)^2}{q(x)}\mathrm{d}x \;, \end{align} from which the claim follows. $\square$

$\endgroup$
3
$\begingroup$

This is probably obvious, but just wanted to explicitly mention the following. It is perhaps more natural to look at the modified $L_2$ norm $L_2'(p,q) = L_2(\sqrt{p}, \sqrt{q})$. Note that probability distributions (which are a subset of unit vectors for the $L_1$ norm) are unit vectors for this modified norm (but need not be unit vectors for the $L_2$ norm). Note that $L_2'$ shares many properties with $L_2$, for example despite the additional $\sqrt{\cdot}$ terms it is still a metric.

Anyway, this modified norm is precisely the Hellinger distance, typically notated $H(p,q) := L_2(\sqrt{p}, \sqrt{q})$. The inequality $H(p,q)^2 \leq D_{KL}(p,q)$ is then known, and can be seen as a refinement of Pinsker's inequality (as $\delta_{TV}(p,q) \leq H(p,q)$ is also known --- I might be missing some small constant factors in some definitions here).

$\endgroup$
2
$\begingroup$

Now, I am trying to answer this question.

Proposition. If $p$ and $q$ are two probability densities, and (upper) bounded by $\tau_1$ and $\tau_2$, respectively, then $$ KL(p,q) \ge \frac{1-\log(2)}{\max(\tau_1, \tau_2)} L_2(p,q). $$

Proof. We define $\eta(x)=\frac{q(x)-p(x)}{p(x)}$, and thus the KL divergence between $p$ and $q$ can be computed as follows. $$ D_{K L}(p || q)=\int_\mathcal{X} p(x) \log \left(\frac{p(x)}{q(x)} \right) d x=-\int_\mathcal{X} p(x) \log (1+\eta(x)) d x. $$ We define \begin{equation} A := \{x \mid \eta(x) > 1\} = \{x \mid q(x)>2p(x)\}, \quad B := \{x \mid \eta(x) \leq 1\} = \{x \mid q(x) \leq 2p(x)\}. \end{equation} Then, we can obtain that

(1) For $x \in A$, $(1+\eta(x)) \leq e^{a\eta(x)}$, where $a=\log(2)$.

(2) For $x \in B$, $(1+\eta(x)) \leq e^{\eta(x)-b\eta(x)^2}$, where $b=1-\log(2)$.

Note that we also have \begin{equation} \int_{\mathcal{X}} p(x) \eta(x) dx = \int_{\mathcal{X}} (q(x)-p(x)) dx = 0, \end{equation} which implies that $\int_A p(x) \eta(x) dx = - \int_B p(x) \eta(x) dx$. Putting all together, we have \begin{equation*} \begin{aligned} D_{K L}(p || q) &=-\int_A p(x) \log (1+\eta(x)) d x-\int_B p(x) \log (1+\eta(x)) d x \newline &\geq -a \int_A p(x) \eta(x) d x-\int_B p(x) \eta(x) d x+b \int_B p(x) \eta(x)^2 d x \newline &=(1-a) \int_A p(x) \eta(x) d x+b \int_B p(x) \eta(x)^2 d x \newline &=(1-\log (2))\left(\int_A|q(x)-p(x)| d x+\int_B p(x)\left(\frac{q(x)-p(x)}{p(x)}\right)^2 d x\right). \end{aligned} \end{equation*} For the first summand in RHS, we have \begin{equation*} \begin{aligned} \int_A|q(x)-p(x)| d x &= \int_A |\frac{q(x)-p(x)}{q(x)}|q(x) d x \newline & \ge \int_A (\frac{q(x)-p(x)}{q(x)})^2 q(x) d x \newline & \ge \frac{1}{\max(\tau_1, \tau_2)} \int_A (q(x)-p(x))^2 d x. \end{aligned} \end{equation*} For the second summand in RHS, we have \begin{equation*} \int_B p(x)\left(\frac{q(x)-p(x)}{p(x)}\right)^2 d x \ge \frac{1}{\max(\tau_1, \tau_2)} \int_B (q(x)-p(x))^2 dx. \end{equation*} Finally, we have \begin{equation*} D_{KL}(p || q) \ge \frac{1-\log(2)}{ \max(\tau_1, \tau_2)} L_2(p, q), \end{equation*} which completes the proof. qed

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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