5
$\begingroup$

I am having a little trouble getting my head around the two "directions" of the Kullback-Leibler divergence:

Definition (Kullback-Leibler divergence) For discrete probability distributions $P$ and $Q$ defined on the same probability space, $\chi$, the Kullback-Leibler divergence from $Q$ to $P$ is defined to be $$D_{KL}(P||Q) := \sum_{x \in \chi}P(x)\log\bigg(\frac{P(x)}{Q(x)}\bigg). $$

Note that The KL-divergence is not really a true distance measure, since it is does not satisfy the Triangle Inequality and $D_{KL}(P||Q)$ does not in general equal $D_{KL}(Q||P)$. Hence the need to distinguish the KL-divergence from its dual, the so-called "reverse KL-divergence".

Fact. Both the KL-divergence and the reverse KL-divergence are examples of f-divergences.

Fact. The KL-divergence is an example of a Bregman divergence.

Question: Is the reverse Kullback-Leibler divergence also a Bregman divergence?

This is not obvious to me. Also, I have read conflicting information, with Amari (2009) arguing that the KL-divergence and its dual are are unique divergences belonging to the $f$-divergence and Bregman divergence classes, and others (e.g., Wang et al. 2019) saying that the reverse KL-divergence is no longer a Bregman. Which is correct?

Any pointers would be greatly appreciated.

References:

  • Wang, Q., Li, Y. and Xiong, J. (2019) Divergence-Augmented Policy Optimization link
  • Amari, S. (2009) $\alpha$-Divergence Is Unique, Belonging to Both $f$-Divergence and Bregman Divergence Classes link
$\endgroup$
8
$\begingroup$

Define the KL convergence as in the Amari's paper linked by you: $$KL(x||y):=D_{KL}(x||y):=\sum(y_i-x_i+x_i\ln\frac{x_i}{y_i}).$$ Then $$KL(x||y)=F(x)-F(y)-\nabla F(y)\cdot(x-y)$$ if $F(x):=\sum(x_i\ln x_i-x_i)$. So, the KL-divergence is a Bregman one.

On the other hand, the dual divergence, defined by $$LK(x||y):=KL(y||x)=\sum(x_i-y_i+y_i\ln\frac{y_i}{x_i}),$$ is not a Bregman one. Indeed, if it were a Bregman one, then for some appropriate function $G$ we would have $$LK(x||y)=G(x)-G(y)-\nabla G(y)\cdot(x-y)$$ and hence $$\nabla_x(LK(x||y))=\nabla G(x)-\nabla G(y),$$ whereas in fact $$\nabla_x(LK(x||y))=(1-y_i/x_i),$$ which cannot be of the form of a difference $\nabla G(x)-\nabla G(y)$ -- because otherwise we would have $(1-v/u)+(1-w/v)=(1-w/u)$ for all positive real $u,v,w$.

(Amari's proof contains formula (52), which contains functions $\psi_\alpha$ and $\psi_{-\alpha}$, supposedly defined by formula (49). However, the expression for $\psi_\alpha$ in (49) is undefined for $\alpha=-1$, whereas it is both of the values $\pm1$ of $\alpha$ that are needed in (52) for $LK$.)

$\endgroup$
3
  • $\begingroup$ Thank you so much! A very clear and informative answer :-) $\endgroup$
    – jw7642
    Mar 18 at 12:04
  • 1
    $\begingroup$ "LK", cute ${}{}{}$ $\endgroup$ Mar 18 at 14:24
  • 2
    $\begingroup$ @jw7642 : So, are you satisfied with this answer? $\endgroup$ Mar 21 at 2:55

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.