4
$\begingroup$

Does the local triangle inequality holds for the Kullback-Leibler divergence? For the local triangle inequality, I mean the $$ d(\theta', \theta) + d(\theta'', \theta) \geq A d(\theta', \theta'') $$ for some $A \in (0,1]$. Also what about the square root of the K-L divergence?

$\endgroup$
3
$\begingroup$

The KL divergence isn't symmetric, so the answer might not be the same depending on how exactly you set up the "local triangle inequality"

For one set-up, the inequality can never be right:

$$ KL(p,q) + KL(p,r) \geq_? A KL(q,r)$$

because here is a counter-example: $p$ a gaussian centered at 0, $q_n$ a mixture of a gaussian centered at 0, and a gaussian centered at -n, with respective probability $\frac{n-1}{n}$ and $\frac{1}{n}$, and $r_n$ a similar mixture but with means 0 and n.

as $n \rightarrow \infty$, $KL(p,q_n) \rightarrow 0$ while $KL(q_n,r_n) \rightarrow \infty$

edit: I figured out a counter-example for the opposite direction

$$ KL(q,p) + KL(r,p) \geq_? AKL(q,r)$$

Once again no, because of another counter-example. Take $q_n$ a gaussian centered at -n, $r_n$ a gaussian centered at +n, and $p_n = 0.5q_n + 0.5r_n$

$KL(q_n,p_n)$ asymptotes to a finite value ($(\sqrt 2 - 1)H(g_0)$ if I'm not mistaken) while $KL(q_n,r_n) \rightarrow \infty$

open question: $KL(q,p) + KL(p,r) \geq_? A KL(q,r)$ ??

| cite | improve this answer | |
$\endgroup$

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.