(Regularized) Dual Representation of Wasserstein-1 metric

Question

Consider $\mathbb{R}^d$, the $d$-dimensional Euclidean space. Let $W_1$ be the $1^{st}$ Wasserstein distance between probability measures $\mu, \nu$ $$W_1(\mu, \nu) = \inf_{\gamma \in \Gamma(\mu, \nu)} \int \|x-y\|_2d\gamma(x,y),$$ where $\Gamma(\mu, \nu)$ is the set of all measures on $\mathbb{R}^d \times \mathbb{R}^d$ with marginals $\mu, \nu$. It is well known that $W_1$ has the following dual representation $$W_1(\mu, \nu) = \sup_{\|f\|_{\text{Lip}} \leq 1} \int f(x)d(\mu-\nu)(x),$$ where $\|f\|_{\text{Lip}} = \sup_{x\neq y} \frac{|f(x)-f(y)|}{\|x-y\|_2}.$ I'm interested in understanding a slight variant of this dual objective $$\sup_{f} \left[\int f(x)d(\mu-\nu)(x) - \frac{M}{2}\|f\|_{\text{Lip}}^2\right],$$ where $M>0$ is a constant. Note that the earlier objective has a constraint on the Lipschitz constant, whereas the latter one has a regularization penalty on the Lipschitz constant.

Is the maximum of the above objective related to the $W_1$ metric? Can we obtain a closed-form expression for the maximum?

Answer 1

I guess I am a bit late, but maybe you are still interested! In any case my thoughts about your regularized expression are the following:

It is easy to show that, $$W_1(\mu, \nu) = -\frac{1}{C^{1/2}} \inf_{\|f\|^2_{\mathrm{Lip}}\leq C}\int f d (\mu-\nu).$$ The optimization problem we then obtain is linear with a convex constrain (the set of bounded Lipschitz functions is convex). Your expression would then be nothing more than the negative of the Lagrangian dual of the optimization problem appearing in the equation above (https://en.wikipedia.org/wiki/Duality_(optimization)). One direct consequence of this is that there is a $C^*$ which depends on $M, \mu, \nu$ and such that $$\sup_{f} \left[\int f(x)d(\mu-\nu)(x) - M\|f\|_{\text{Lip}}^2\right] = (C^{*})^{2} W_1(\mu, \nu).$$