Earth Movers Distance and Maximum Mean Discrepency

Question

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.

Answer 1

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.