Is there an inequality relation between KL-divergence and $L_2$ norm?

Question

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

Answer 1

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

Answer 2

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$

Answer 3

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

Answer 4

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