2
$\begingroup$

Can someone who read WGAN/WAE papers and understood Wasserstein part, could you share how you prepared necessary Optimal Transport background?

The mentioned papers seem little tough if you don't have an intuition on Wasserstein metric/optimal transport theory. The papers mostly cite some books on optimal transport - I don't think I'd be able to go through a whole book, but I wasn't able to find accessible tutorials on the topic.

Alternatively, could anyone narrow the specific topics that are needed to understand these papers? I've seen that they use Kantorovich duality - can one read Villani's book mostly concentrating on that? Would it be sufficient to understand the papers?

$\endgroup$
1
$\begingroup$

For WGAN paper these are needed:

  • Optimal transport problem statement:

    • Given two probability measures $\mu, \nu$ on compact $X, Y$, $c: X \times Y \to \mathbb{R}^+$ continuous find $$p \in P_{\mu, \nu}$$ that minimizes $$Ec = \int c(x,y) dp(x,y)$$ where

      $P_{\mu, \nu} = \{$ probability measure on $X \times Y$ with marginals $\mu, \nu \}$

  • Optimal transport problem has a solution *
  • Kantorovich duality (general) $$\inf_{c \in P_{\mu, \nu}} Ec = \sup_{f, g \in L^1} \int f d\mu + \int g d\nu$$
  • Kantorovich duality when $c$ is a metric on $X$ (in this case$X=Y$): $$\inf_{c \in P_{\mu, \nu}} Ec = \sup_{f, g} \int f d\mu - \int f d\nu$$ where the $sup$ range is over 1-Lipschitz functions on $X$.

WGAN paper

The authors use second form of Lipschitz duality. The $f$ is output of the discriminator, and it is guaranteed to be $d$-Lipschitz because of weight clipping **.

* - The set of $p$ that satisfy constraint on marginals is tight, and from Prokhorov's theorem it follows that it's precompact, and in fact it's also closed, thus it is compact, so $E$ attains infimum on $P_{\mu, \nu}$.

** - weight clipping makes weight space $\Theta$ compact, and the space of possible discriminator $f$s is parametrized continuously by this space, so function $$\Theta \to \mathbb{R}^+$$

$$\theta \to \inf \{d \in \mathbb{R}^+| f_{\theta}\ is\ d-Lipschitz\}$$

Attains its minimum.

Books

I've checked out two Villani's books:

  • Optimal Transport: Old and New (the one I mentioned)
  • Topics in Optimal Transportation

Personally I found that second one has better pace - it gets to Kantorovich duality almost right away (in 1st chapter), and it is really good for getting intuition, as it first sketches the needed proofs, and fills in details later.

$\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.