Answers.Body: <p>To prove that the KL divergence does not satisfy the triangle inequality, you just need a <a href="http://www.math.toronto.edu/writing/Counterexample.pdf" rel="nofollow noreferrer">counterexample</a>. </p>
  
  <h2>Definitions</h2>
  
  <h3>KL divergence</h3>
  
  <p>Let's first recapitulate the definition of KL divergence for discrete probability distributions <span class="math-container">$p$</span> and <span class="math-container">$q$</span> (for simplicity).</p>
  
  <p><span class="math-container">$$ 
  D_{\text{KL}}(p\parallel q)
  =
  \sum_{x\in {\mathcal {X}}}
  p(x)\log 
  \left(
  \frac {p(x)}{q(x)}
  \right)
  $$</span></p>
  
  <h3>Triangle inequality</h3>
  
  <p>Let's also recap the definition of the <a href="https://en.wikipedia.org/wiki/Metric_(mathematics)" rel="nofollow noreferrer">triangle inequality</a> for distance <span class="math-container">$d$</span>, which can be expressed as</p>
  
  <p><span class="math-container">$$
  d(p,q) \leq d(p, r) + d(r, q),
  $$</span>
  where <span class="math-container">$p, q$</span> and <span class="math-container">$r$</span> are probability distributions. </p>
  
  <h2>Proof</h2>
  
  <p>For simplicity, let the sample space be <span class="math-container">$\mathcal{X} = \{0, 1 \}$</span>. Consider now the following three discrete probability distributions.</p>
  
  <p><span class="math-container">$$
  p(x)=
  \begin{cases}
  \frac{1}{2}&amp; \text{if } x = 0\\
  \frac{1}{2}&amp; \text{if } x = 1
  \end{cases}
  $$</span></p>
  
  <p><span class="math-container">$$
  r(x)=
  \begin{cases}
  \frac{1}{4}&amp; \text{if } x = 0\\
  \frac{3}{4}&amp; \text{if } x = 1
  \end{cases}
  $$</span></p>
  
  <p><span class="math-container">$$
  q(x)=
  \begin{cases}
  \frac{1}{10}&amp; \text{if } x = 0\\
  \frac{9}{10}&amp; \text{if } x = 1
  \end{cases}
  $$</span></p>
  
  <p>Let's now apply the definition of the triangle inequality and the KL divergence for these discrete probability distributions. So, we want to show the following inequality does <strong>not</strong> hold.</p>
  
  <p><span class="math-container">$$
  D_{\text{KL}}(p\parallel q) 
  \leq 
  D_{\text{KL}}(p\parallel r) 
  + 
  D_{\text{KL}}(r\parallel q)
  $$</span></p>
  
  <p>which can be expanded to</p>
  
  <p><span class="math-container">\begin{align}
  \sum_{x\in \{0, 1 \}}
  p(x)\log 
  \left(
  \frac {p(x)}{q(x)}
  \right)
  &amp;\leq 
  \sum_{x\in \{0, 1 \} }
  p(x)\log 
  \left(
  \frac {p(x)}{r(x)}
  \right)
  + 
  \sum_{x\in \{0, 1 \}}
  r(x)\log 
  \left(
  \frac {r(x)}{q(x)}
  \right) 
  \end{align}</span></p>
  
  <p>which roughly corresponds to</p>
  
  <p><span class="math-container">\begin{align}
  0.51 &amp;\leq 0.14 + 0.09 \\
  0.51 &amp;\leq 0.24
  \end{align}</span>
  which is clearly false. </p>
  
  <p>Given that the triangle inequality does not hold in one case, it doesn't hold in all cases, so the triangle inequality does not hold for the KL divergence.</p>
  
  <p><span class="math-container">$$\tag*{$\blacksquare$}$$</span></p>
  
  <p>For reproducibility, I have used the following Python (3.7) program to compute the KL divergences.</p>
  
  <pre><code>from math import log
  
  one = (1 / 2 * log((1 / 2) / (1 / 10))) + (1 / 2 * log((1 / 2) / (9 / 10)))
  two = (1 / 2 * log((1 / 2) / (1 / 4))) + (1 / 2 * log((1 / 2) / (3 / 4)))
  three = (1 / 4 * log((1 / 4) / (1 / 10))) + (3 / 4 * log((3 / 4) / (9 / 10)))
  
  print(one)
  print(two)
  print(three)
  print(two + three)
  print(one &lt;= two + three)
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-04T21:02:28.543Z
Answers.Text: There may be cases where it holds, but a single counter example is a sufficient disproof on its own.
Answers.UserDisplayName: EngrStudent
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-09T23:29:30.303Z
Answers.Text: Is there any variant of the triangle inequality that does hold?
Answers.UserDisplayName: a06e
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-14T14:07:01.940Z
Answers.LastActivityDate: 2020-02-14T23:49:51.847Z
Answers.LastEditDate: 2020-02-14T23:49:51.847Z
Answers.UserDisplayName: nbro
Body: <p>The KL divergence is defined as</p>
  <p><span class="math-container">$$D_{KL}=\sum_i p(x_i)log\left(\frac{p(x_i)}{q(x_i)}\right)$$</span></p>
  <p>Why does <span class="math-container">$D_{KL}$</span> not satisfy the triangle inequality?</p>
  <p>Also, can't you make it satisfy the triangle inequality by taking the absolute value of the information at every point?</p>
  
Tags: <proofs><variational-autoencoder><kl-divergence>
Title: Why does the KL divergence not satisfy the triangle inequality?
UserDisplayName: user8714896
ThreadText: # Why does the KL divergence not satisfy the triangle inequality?
  
  (Asked by: username_0 on 2020-02-14)
  
  The KL divergence is defined as
  
  $$D\_{KL}=\sum\_i p(x\_i)log\left(\frac{p(x\_i)}{q(x\_i)}\right)$$
  
  Why does $D\_{KL}$ not satisfy the triangle inequality?
  
  Also, can't you make it satisfy the triangle inequality by taking the absolute value of the information at every point?
  
  **Tags:** proofs, variational-autoencoder, kl-divergence
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-14. Score: 3 | Accepted answer
  
  To prove that the KL divergence does not satisfy the triangle inequality, you just need a counterexample. 
  Definitions
  KL divergence
  Let's first recapitulate the definition of KL divergence for discrete probability distributions $p$ and $q$ (for simplicity).
  $$ 
  D_{\text{KL}}(p\parallel q)
  =
  \sum_{x\in {\mathcal {X}}}
  p(x)\log 
  \left(
  \frac {p(x)}{q(x)}
  \right)
  $$
  Triangle inequality
  Let's also recap the definition of the triangle inequality for distance $d$, which can be expressed as
  $$
  d(p,q) \leq d(p, r) + d(r, q),
  $$
  where $p, q$ and $r$ are probability distributions. 
  Proof
  For simplicity, let the sample space be $\mathcal{X} = \{0, 1 \}$. Consider now the following three discrete probability distributions.
  $$
  p(x)=
  \begin{cases}
  \frac{1}{2}& \text{if } x = 0\\
  \frac{1}{2}& \text{if } x = 1
  \end{cases}
  $$
  $$
  r(x)=
  \begin{cases}
  \frac{1}{4}& \text{if } x = 0\\
  \frac{3}{4}& \text{if } x = 1
  \end{cases}
  $$
  $$
  q(x)=
  \begin{cases}
  \frac{1}{10}& \text{if } x = 0\\
  \frac{9}{10}& \text{if } x = 1
  \end{cases}
  $$
  Let's now apply the definition of the triangle inequality and the KL divergence for these discrete probability distributions. So, we want to show the following inequality does not hold.
  $$
  D_{\text{KL}}(p\parallel q) 
  \leq 
  D_{\text{KL}}(p\parallel r) 
  + 
  D_{\text{KL}}(r\parallel q)
  $$
  which can be expanded to
  \begin{align}
  \sum_{x\in \{0, 1 \}}
  p(x)\log 
  \left(
  \frac {p(x)}{q(x)}
  \right)
  &\leq 
  \sum_{x\in \{0, 1 \} }
  p(x)\log 
  \left(
  \frac {p(x)}{r(x)}
  \right)
  + 
  \sum_{x\in \{0, 1 \}}
  r(x)\log 
  \left(
  \frac {r(x)}{q(x)}
  \right) 
  \end{align}
  which roughly corresponds to
  \begin{align}
  0.51 &\leq 0.14 + 0.09 \\
  0.51 &\leq 0.24
  \end{align}
  which is clearly false. 
  Given that the triangle inequality does not hold in one case, it doesn't hold in all cases, so the triangle inequality does not hold for the KL divergence.
  $$\tag*{$\blacksquare$}$$
  For reproducibility, I have used the following Python (3.7) program to compute the KL divergences.
  from math import log
  
  one = (1 / 2 * log((1 / 2) / (1 / 10))) + (1 / 2 * log((1 / 2) / (9 / 10)))
  two = (1 / 2 * log((1 / 2) / (1 / 4))) + (1 / 2 * log((1 / 2) / (3 / 4)))
  three = (1 / 4 * log((1 / 4) / (1 / 10))) + (3 / 4 * log((3 / 4) / (9 / 10)))
  
  print(one)
  print(two)
  print(three)
  print(two + three)
  print(one <= two + three)
  
  > **Comments:**
  > **username_2**: There may be cases where it holds, but a single counter example is a sufficient disproof on its own.  
  > **username_3**: Is there any variant of the triangle inequality that does hold?  
  
  ---
  
  