Skip to main content
Corrected 3 appearances of max(\tau_1,\tau_2), where it should be 1/max(\tau_1,\tau_2).
Source Link

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 \max(\tau_1, \tau_2) \int_A (q(x)-p(x))^2 d x. \end{aligned} \end{equation*}\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 \max(\tau_1, \tau_2) \int_B (q(x)-p(x))^2 dx. \end{equation*}\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 (1-\log(2)) \max(\tau_1, \tau_2) L_2(p, q), \end{equation*}\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

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 \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 \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 (1-\log(2)) \max(\tau_1, \tau_2) L_2(p, q), \end{equation*} which completes the proof. qed

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

Source Link
Ze-Nan Li
  • 175
  • 1
  • 7

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 \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 \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 (1-\log(2)) \max(\tau_1, \tau_2) L_2(p, q), \end{equation*} which completes the proof. qed