7
$\begingroup$

By Kantorovich-Rubinstein duality the Earth Movers Distance (EMD)/Wasserstein Metric is equivalent to Maximum Mean Discrepancy (MMD) correct? See here for a more thorough explanation. Why then does the original Kernel MMD paper compare their method to EMD (see the first paragraph in section 7.2) and corresponding lectures by people like Alex Smola seem to imply that they are different metrics. I feel like I'm going crazy because I always assumed that everyone knew that MMD and EMD were the same via the Wasserstein GAN paper (granted Gretton et. al. published way before WGAN was introduced, but I can't find anyone referencing the equality even with a google search now), but now reading these papers I feel like up is down and down is up.

$\endgroup$
2
  • $\begingroup$ You mean "equivalent" in the sense that these metrics are integral probability metrics? Then they are equivalent. But Gretton et.al. discuss MMD for Reproducing Kernel Hilbert Spaces (RKHS). In case of EMD the unit ball is made of Lipschitz functions with $L\leq 1$. This is not a RKHS, So it makes sense to compare. Or do you mean "equivalent metrics" in the topological sense? This would not follow from duality and I don't think it is true in general. $\endgroup$
    – g g
    Jun 14, 2019 at 21:21
  • 1
    $\begingroup$ So I mean equivalent in the topological sense, although I also mean theoretically as I understand MMD with a RKHS will not give the same answer as the Wasserstein distance with at Lipschitz 1 neural network. I was under the impression that the Wasserstein GAN proof showed that, theoretically (if you could compare every possible Lipschitz <= 1 function), this was equivalent to the EMD. Is my understanding off? If you have a good explanation of these you can make it an answer and I will mark your answer as answered. $\endgroup$
    – www3
    Jun 20, 2019 at 17:02

1 Answer 1

7
$\begingroup$

No, they are not the same.

First, let's start with a more general framework to motivate the use of EMD or MMD. Suppose we want to fit a family $(\mu_{\theta})_{\theta}$ of parametric distributions to an empirical one $\nu$, which means we want to solve the following minimisation problem: $$\min_{\theta} \mathcal L(\mu_{\theta}, \nu)$$ where $\mathcal L$ measures the difference between two distributions. For example, if $\mathcal L$ is the Kullback-Leibler divergence, this is asymtotically equivalent to the usual maximum likelihood framework. Or when $\mathcal L$ is a $\phi$-divergence (I omit the detail of the function $\phi$), then we recover the infamous original GAN.

Now, WGAN is nothing but picking $\mathcal L$ to be Wasserstein distance, or more precisely, $1$-Wasserstein distance, aka EMD (there are also $p$-Wasserstein distances, for $p \geq 1$, but they are all equivalent metrics, under some mild conditions). The maximisation in the minimax problem is just the dual form of EMD.

(Bonus: if you pick $\mathcal L$ to be MMD, then you will find something called "Generative moment matching networks" but do NOT confuse with MMD-GAN, they are close but the latter is a generalisation of the former).

Next, let see how MMD and EMD are different.

  • They both belong to the family called Integral Probability Metrics, which means something of the form \begin{align*} d_{\mathcal F} (\mu, \nu) = \sup_{f \in \mathcal F} \Big( \int f d\mu - \int f d\nu \Big) \end{align*} For example, if $\mathcal F$ is a kernel function from the unit ball of the kernel-reproducing hilbert-space, then we recover MMD. Or if $\mathcal F$ is the set of $1$-Lipschitz functions, then we recover EMD in dual form. What special about this family is that under some mild conditions, it characterizes the convergence in law: $\mu_n \overset{\mathcal D}{\longrightarrow} \mu \Leftrightarrow d_{\mathcal F} (\mu_n, \mu) \to 0$. So MMD and EMD are equivalent in this sense. This is NOT true for Kullback-Leibler or total variation.

  • Another way to see their difference (which I find more clear) is via the entropic regularisation defined as \begin{align*} L_{c, \epsilon}(\mu, \nu):= \min_{P \in \Pi(\mu, \nu)}\langle C, P \rangle + \epsilon H(P) \end{align*} For now, let's omit everything in the definition. What we care is when $\epsilon = 0$, we recover the definition of EMD (or more correctly optimal transport distance). When $\epsilon \to \infty$, we recover MMD.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer, could you explain what are C and P and PI(mu, nu) in the last equation ? $\endgroup$ Jun 11, 2020 at 5:46
  • 1
    $\begingroup$ @AlbertJamesTeddy: you can have a look at the book "Computational optimal transport" for all details. $\endgroup$
    – SiXUlm
    Jun 17, 2020 at 7:44
  • 1
    $\begingroup$ @SiXUlm can you please provide a reference to read more on the case when $\epsilon \to \infty$? $\endgroup$ Apr 6, 2021 at 10:46
  • $\begingroup$ @NovinShahroudi: you may have a look at the section on Sinkhorn divergence here: mathematical-tours.github.io/book-sources/optimal-transport/… $\endgroup$
    – SiXUlm
    Apr 6, 2021 at 13:40

Your Answer

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

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