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?


1 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).$$


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.