7
$\begingroup$

I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.

More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$ be a uniform distribution on $\Xi$, namely, $\nu_{ij}:=\nu(\{(i,j)\})=\frac{1}{N^2}$, for all $1\leq i,j\leq N$. Consider the problem \begin{equation} \max_{\mu\geq0} \bigg \{ W(\mu,\nu):\ \sum_{i}\mu_{ij} = \frac{1}{N}, \forall j,\ \sum_{j} \mu_{ij}=\frac{1}{N}, \forall i \bigg\}, \tag{1} \end{equation} where $W_1(\mu,\nu)$ is the Wasserstein distance between probability distribution $\mu:=\{\mu_{ij}\}_{1\leq i,j\leq N}$ and $\nu$, defined as $$ W_1(\mu,\nu) := \min_{\pi\geq0} \bigg\{\sum_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||_1 \pi_{(i,j),(i',j')}:\ \sum_{i,j} \pi_{(i,j),(i',j')} = \nu_{i'j'},\forall i',j',\ \sum_{i',j'} \pi_{(i,j),(i',j')} = \mu_{ij},\ \forall i,j\bigg\}. $$

My conjecture is that the maximizer of problem $(1)$ is given by $\mu_{ij}=\frac{1}{N}{1}_{\{i=j\}}$, or $\mu_{ij}=\frac{1}{N}{1}_{\{i+j=N+1\}}$, namely, the comonotonic/countermonotonic distribution. But how to prove/disprove it? Also, if it is true, could the result be extended to the multivariate case, namely, $\Xi=\{1,2,\ldots,N\}^K$ for $K>2$, or be extended for norms other than $\ell_1$-norm, or other $W_p$ distance ($p>1$)?

Update: Steve provides an affirmative answer for $\ell_1$-norm with $W_1$ distance in the case of $K=2$, and I provide a proof for $\ell_2$ norm with $W_2$ distance for all $K\geq2$. I am wondering if we can get some other result, such as $\ell_1$-norm with $K>2$, or $\ell_\infty$-norm.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ If I'm not mistaken, permutation measures $\frac{1}{N} \sum_i \delta_{i \sigma(i)}$ are exactly the extremal points of the polytope of the probability measures with uniform marginals. And the maximum distance (to any distribution, in particular, to the uniform one) should be obtained at one of these points. $\endgroup$
    – Victor Kleptsyn
    Mar 10, 2017 at 1:17
  • $\begingroup$ @VictorKleptsyn Yes, you're right. Essentially we want to maximize a convex function over a convex set, thus the maximum would be obtained at an extreme point, and in two dimensional case, this is the permutation matrix. However, since maximizing a convex function is generally hard, we cannot expect a solution for arbitrary distribution $\nu$, but I hope for some special $\nu$ such as the uniform distribution, we can obtain some result. $\endgroup$
    – O. Richard
    Mar 10, 2017 at 2:01
  • $\begingroup$ The maximizer might not be unique. Have you considered the case where $\mu$ is the identity coupling (comonotonic distribution in your words), and $\nu$ is uniform over the set $j=i+N/2$ modulus $N$ ($N$ even)? A rough estimate seems to indicate both $\nu$ and the ``countermonotonic'' distribution are at distance $1/2$ (for some, maybe all $p$) of $\mu$. $\endgroup$
    – Benoît Kloeckner
    Mar 10, 2017 at 11:48
  • 1
    $\begingroup$ @BenoîtKloeckner I just check $N=4$ by solving the linear programming that defines Wasserstein distance. The distance between comonotonic distribution and $\nu$ is 0.25, whereas the distance between uniform distribution on $j=i+N/2 \mod N$ and $\nu$ is 0.2. $\endgroup$
    – O. Richard
    Mar 10, 2017 at 14:58
  • 1
    $\begingroup$ The graph of $j=i+N/2$ has a larger "neighborhood". I wonder if $i=j$ and $i+j=N+1$, being straight lines, have the smallest neighborhood by some "isoperimetric" theorem? $\endgroup$
    – Bjørn Kjos-Hanssen
    Mar 10, 2017 at 16:09

2 Answers 2

Reset to default
2
$\begingroup$

I think I have an answer for the case p = 1, K = 2. I write "I think" because my computation does not coincide with the example values for $N=4$ posted earlier by OP in a comment, but I really cannot find any error in my proof, so I wanted to share it.

As already mentioned, we only need to consider permutation measures of the form $\mu = \sum_{i=1}^N \frac{1}{N} \delta_{i,\sigma(i)}$, since these are the extremal points of the set we optimize over.

For any such $\mu$, we can define a coupling $\pi$ by $\pi_{(i,\sigma(i)),(i,j)} = 1/N^2$ for $i,j \in \{1,...,N\}$ and $\pi_{(i,j),(i',j')} = 0$, if $i,j,i',j'$ are not of the form as before. That this is an admissible coupling in the definition of $W_1$ is trivial. The corresponding "value" is $$ \sum_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||_1 \pi_{(i,j),(i',j')} = \sum_{1 \leq i,j' \leq N} |\sigma(i) - j'| \frac{1}{N^2}. $$ We further show that this value is minimal if $\mu$ is the monotonic or comonotonic measure, which will yield the claim. I only show this for the monotonic case, $\mu = \frac{1}{N}\sum_{i=1}^N \delta_{i,i}$. Then for any admissible coupling $\hat{\pi}$, by the constraints in the calculation of the Wasserstein distances, we see \begin{align*} \sum_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||_1 \hat{\pi}_{(i,j),(i',j')} =& \sum_{1\leq i',j' \leq N} \sum_{1 \leq i \leq N} ||(i,i)-(i',j')||_1 \hat{\pi}_{(i,i),(i',j')} \\ \geq& \sum_{1\leq i',j' \leq N} \sum_{1 \leq i \leq N} ||(i',i')-(i',j')||_1 \hat{\pi}_{(i,i),(i',j')}\\ =&\sum_{1\leq i',j' \leq N} |i'-j'| \frac{1}{N^2}, \end{align*} where the inequality is elementwise and the last term corresponds to the value for the coupling $\pi$.

Note that this only shows that monotonic/comonotonic measures are maximizers, but not that these are the only maximizers.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your answer. It seems that in your optimal coupling $\pi$ for computing $W_1$, the probability mass on $(i,\sigma(i))$ is only allowed to split in the same row. Why? This is not true for $\ell_2$-norm, but may be correct for $\ell_1$. $\endgroup$
    – O. Richard
    Mar 12, 2017 at 22:54
  • $\begingroup$ I think if we can prove that the optimal coupling between uniform and comonotonic distribution is indeed given by $\pi$, then combining with your answer we can obtain a proof. I know one optimal coupling between uniform and comonotonic distribution is given by the monotone coupling which is different from $\pi$, but maybe due to the specialty of $\ell_1$-norm, $\pi$ is also an optimal coupling. I have tested on $N=4$ and they give the same value. $\endgroup$
    – O. Richard
    Mar 12, 2017 at 23:11
  • $\begingroup$ The coupling $\pi$ is only optimal for the monotonic/comonotonic case. As you mentioned, this only works with the $l_1$ norm. For the $l_1$ norm, we can visualize going from the diagonal to the other lattice points in $\{1,...,N\}^2$ in horizontal/vertical steps, and the $l_1$ norm is just the number of steps. The idea was, if we are going over from the monotonic distribution to the uniform distribution, any coupling that moves mass strictly away from the diagonal is going to be optimal, and the simplest of those is just $\pi$. $\endgroup$
    – Steve
    Mar 12, 2017 at 23:42
  • $\begingroup$ How do you describe "strictly away" rigorously? $\endgroup$
    – O. Richard
    Mar 12, 2017 at 23:51
  • $\begingroup$ Well, this was just the intuition for the proof. It is not needed. But what I meant is that if $\hat{\pi}$ is any optimal coupling for the monotonic distribution, then we should have $\hat{\pi}_{(i,i),(i',j')} = 0$ if $||(i,i)-(i',j')||_1 > ||(i',i')-(i',j')||_1$. I.e. if we cannot go from (i,i) to (i',j') by always going away from the diagonal, then $\hat{\pi}_{(i,i),(i',j')}$ should be zero. $\endgroup$
    – Steve
    Mar 12, 2017 at 23:59
2
$\begingroup$

It is an interesting question.

Actually your guess about dependence on measurement parameter $p$ is correct. The minimal Wasserstein distance between two copulas (In your case the collection of all probability distributions with same uniform marginals is a copula, which also includes the 2-d uniform distribution. Let us denote the 2-d uniform distribution by $\pi_0$ in following discussion.) actually depends on the measurement parameter $p$ of the Wasserstein distance. See Prop 1.1 of Alfonsi&Jourdain. So it is not hard to see that the maximal Wasserstein distance will also depend on $p$ using the "coarest" Fréchet–Hoeffding copula bounds on each dimension of marginals and hence the calculation of Wasserstein distance. A concrete example where $p=2$ can be found in [Cuesta-Albertos et.al].

Now come to the other part of your question that what is the maximal Wasserstein distance to $\pi_0$. Then it is equivalent to find geodesics on the submanifold determined by copula $C_{unif}$ on the probability space metricized by Wasserstein distance. This problem is generally unsolved, if you do not restrict the family of probability distributions under consideration, to my best knowledge.

One noticeable attempt is [Ambrosio et.al] whose work is also on $p=2$. If you metricized this copula, then I think you only need to find the complementary geodesic in a circular neighborhood of $\pi_0$(geodesics in a circular neighborhood of $pi_0$ correspond to the distributions possessing the minimal Wasserstein ($L^2$) distances to $\pi_0$ ) Again for general case $p\neq 2$ I am also interested in knowing more.

One more comment is that Wasserstein distance is a measure of dissimilarity, and thus we usually talk about its minimization instead of maximization. OP seems asking a bound on Wasserstein distance for a general family. As you said in the comment, if the motivation is only a convex optimization problem, I was wondering if it could be re-phrase into a minimization problem by some sort of duality.

Reference

[Alfonsi&Jourdain]Alfonsi, Aurélien, and Benjamin Jourdain. "A remark on the optimal transport between two probability measures sharing the same copula." Statistics & Probability Letters 84 (2014): 131-134.

[Cuesta-Albertos et.al]Cuesta-Albertos, Juan A., Carlos Matrán Bea, and Jesús M. Rodríguez Rodríguez. "Shape of a distribution through the L2-Wasserstein distance." Distributions With Given Marginals and Statistical Modelling. Springer Netherlands, 2002. 51-61.

[Ambrosio et.al]Ambrosio, Luigi, Nicola Gigli, and Giuseppe Savaré. "Gradient flows with metric and differentiable structures, and applications to the Wasserstein space." Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni 15.3-4 (2004): 327-343.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. I have several questions: (1) Could you be more specific on which example in [Cuesta-Albertos et.al] for maximal Wasserstein distance? (2) For the "unsolved" general problem, do you mean it is still unsolved even if it is for uniform $C_{unif}$, or just for a general copula? (3) What is a circular neighborhood? $\endgroup$
    – O. Richard
    Mar 12, 2017 at 2:14
  • $\begingroup$ (1)[Cuesta-Albertos et.al] discussed how to figuring out the shape of a copula using minimization of Wasserstein distance. (2)For general copula it is not solved, for $C_{unif}$ I do not know and want to know if you happen to figure out. (3) Circular nbd is a kind of nbd similar to $\epsilon$-neighborhood when the manifold has positive curvature, you can use $\epsilon$-net in some circumstances to replace it. See Example 3.4.2 in Differential Geometry of Curves and Surfaces: A Concise Guide by Victor Andreevich Toponogov, for example. $\endgroup$
    – Henry.L
    Mar 12, 2017 at 2:29
  • $\begingroup$ @O.Richard see my update in the last paragraph and the first paragraph(a serious typo there). $\endgroup$
    – Henry.L
    Mar 12, 2017 at 2:34
  • $\begingroup$ Thanks for your update. I just read the references and hope to get some idea. In fact, I think for $W_2$ we can explicitly compute the Wasserstein distance, and reduce the problem to a matrix problem. See my posted answer and let me know if it is correct. My main interest is using $\ell_1$ norm. Also note that the $p$ in $\ell_p$ is NOT the order of Wasserstein distance, but merely the metric of the space where the random variable takes value. I modified the question to make it clear. $\endgroup$
    – O. Richard
    Mar 12, 2017 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.