9
$\begingroup$

Consider the Wasserstein metric of order one $W_1$ (a.k.a. the Earth Movers Distance). I would like to know whether it is possible to link $W_1$ and Kullback–Leibler divergence (a.k.a. relative entropy) and what this would mean intuitively. I can't find it anymore, but if I am not mistaken the following holds true for some constant $C$ $$ W_1(\mu, \nu)\le \sqrt{C\cdot \text{KL}(\nu ||\mu)}, $$

where $\text{KL}$ is the KL-divergence. My first question would be: Is the above-mentioned inequality true? Secondly, how should one interpret this estimation?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I am looking for inequalities relating W_p to KL (ideally in the direction opposite to yours), so if you find references please answer your own question and include them here. Thanks $\endgroup$
    – Coca
    Sep 21, 2019 at 17:25
  • $\begingroup$ You might want to have a look at this paper >>> arxiv.org/abs/1709.10219 Didn't read more than the abstract but seems relevant. $\endgroup$
    – can't stop me now
    Jan 23, 2020 at 1:53
  • $\begingroup$ For an explicit example where the inequality fails see the example in my answer here: stats.stackexchange.com/a/295729/150025 in that Gaussian example, taking $w$ to be arbitrarily close to $0$ but still positive will violate the inequality stated. $\endgroup$
    – Lucas Roberts
    Mar 13, 2021 at 15:28

2 Answers 2

Reset to default
6
$\begingroup$

This post gives inequalities for a bunch of distances, including total variation $$\frac{1}{2}d_{TV}(\nu,\mu)<\sqrt{KL(\nu,\mu)}$$ and this says the Wasserstein distance is bounded by the total variation distance $$2W_1(\nu,\mu)\leq Cd_{TV}(\nu,\mu)$$ if the metric is bounded by $C$.

There isn't a simple bound in the other direction, since you can make the KL divergence infinite by moving the probability off an arbitrarily small spot onto the neighbouring area, and this can be done with arbitrarily small $W_1$ distance. For example, take two standard Normals. For one of them, set the density to zero on $[0,\epsilon]$ and to twice the existing value on $[-\epsilon,0]$. Do the opposite for the other one. The Wasserstein distance is proportional to $\epsilon$, but the KL-divergence is infinite.

Improve this answer
$\endgroup$
4
$\begingroup$

As was pointed out in the previous post this inequality is not true in general. However, there has been a lot of research on those measures $\mu$ for which it is true for all measures $\nu$. Most prominently this holds for the standard normal distribution.
Those kinds of estimates go under 'Talagrand inequality'. Take a look at the paper of Otto and Villani and refernces therein: http://cedricvillani.org/sites/dev/files/old_images//2012/08/014.OV-Talagrand.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.