Kantorovich Duality — Alex Beaudin

This post covers optimization problems over probability distributions. It turns out all expected value problems are linear in the distribution, but they are also infinite-dimensional! To solve the, we need to find a relaxation or a trick that would cast the problem in a finite-dimensional setting. As we will cover, this is indeed possible by looking at the optimization problem’s dual.

The Kantorovich Problem and its Dual

This post has a lot of definitions. While we state everything formally, we do not expect the reader to be familiar with everything. Notes permeate this blog to provide a mental model for stated definitions.

First, the problem statement. Kantorovich was interested in generalizing Monge’s Earth mover’s problem. In essence, how can we transport one mass of objects in a particular configuration to a new configuration with least energy? Kantorovich formalized it in such a way to allow for mass to split.

Definition.Kantorovich Primal Problem

Fix Polish spaces $X, Y$ , marginals $\mu \in \mathcal{P}(X), \nu \in \mathcal{P}(Y)$ , and a cost $c: X \times Y \to \R \cup \{+\infty\}$ that is lower semi-continuous. The primal is the following linear program over couplings:

\begin{aligned} \inf_{\pi \in \mathcal{P}(X \times Y)} \quad & \int_{X \times Y} c d\pi \\ \text{s.t.} \quad & \pi(A \times Y) = \mu(A) \text{ for all } A \subseteq X \\ & \pi(X \times B) = \nu(B) \text{ for all } B \subseteq Y. \end{aligned} \tag{P}

This is a proper dual if we have weak-duality, so let’s show that. Strong duality requires some additional properties, which we will discuss later.