On the existence of Monge solutions to multi-marginal optimal transport with quadratic cost and uniform discrete marginals

Given probability measures $\mu_{1},\mu_{2},...,\mu_{N}$ (known as the marginals) on respective bounded domains $X_{1},X_{2},...,X_{N}\subseteq\mathbb{R}^{d}$ and a cost function $c:X_{1}\times X_{2}\times...\times X_{N}\rightarrow\mathbb{R}$, the multi-marginal optimal transport problem is to minimize

over the set $\Pi(\mu_{1},\mu_{2},...,\mu_{N})$ of probability measures on $X_{1}\times X_{2}\times...\times X_{N}$ whose marginals are the $\mu_{i}$. In particular, the $N=2$ case is the classical optimal transport problem, which represents a very active area of modern mathematics, with many applications, reviewed in, for example [27, 25, 28]. The more general case, $N\geq 3$, has recently emerged as an important problem in its own right, owing largely to it own wide variety of applications; see, for instance, the survey papers [19, 8].

A central question in this theory is whether minimizers concentrate on the graphs of functions over the first variable $x_{1}$; solutions with this structure are known as Monge solutions. Restricting the minimization to measures arising from such mappings, or, adopting the terminology of [9], making the Monge ansatz, when justified, amounts to a spectacular dimensional reduction and therefore greatly simplifies the problem computationally. In the classical $N=2$ case, it is well known that if $\mu_{1}$ is absolutely continuous with respect to Lebesgue measure, then, for cost satisfying mild structural conditions, the solution to (1) is unique and of Monge type [4, 11, 15]. Central among such costs is the quadratic cost, $c(x_{1},x_{2})=|x_{1}-x_{2}|^{2}$, which induces a metric, known as the Wasserstein distance, on the set of probability measures, defined by $W_{2}(\mu_{1},\mu_{2}):=\sqrt{\inf_{\gamma\in\Pi(\mu_{1},\mu_{2})}\int_{X_{1}\times X_{2}}|x_{1}-x_{2}|^{2}\,d\gamma}$; Monge solution and uniqueness results for this cost were first proven by Brenier [3]. The situation is much more subtle and less well understood when $N\geq 3$. However, by now many examples of cost functions for which unique Monge solutions exist for absolutely continuous marginals [5, 12, 7, 22, 20], as well as many for which they do not [6, 18, 17], have been discovered, and some general (though very strong) conditions on $c$ ensuring this structure have been developed [16, 14, 21]. Of special note is the natural, multi-marginal extension of the quadratic cost,

or equivalently, $c(x_{1},x_{2},...,x_{N})=-\left|\sum_{i=1}^{N}x_{i}\right|^{2}$, for which existence of Monge solutions and uniqueness were proven by Gangbo and Swiech [10]. Solving (1) with this cost is known to be equivalent to finding a Wasserstein barycenter (with equal weights on the measures), which, as introduced by Agueh-Carlier [1], is a minimizer among probability measures $\nu$ on $\mathbb{R}^{d}$ of

Wasserstein barycenters are Fréchet means on the Wasserstein space, and are an extremely active area of current research, due to many applications in statistics, image processing and data science, among other areas (see, for instance, [24, 13, 29, 26] and the survey in the monograph [23]).

In this short note we are interested in discrete, rather than absolutely continuous, marginals $\mu_{i}$. In general, optimal couplings between discrete measures need not be unique or of Monge type; indeed, in general, there may not even exist a single coupling $\gamma\in\Pi(\mu_{1},\mu_{2},...,\mu_{N})$ which is of Monge type. However, such transport maps at least exist when all the marginals are uniformly distributed on a common number $m$ of points, as is often the case in applications. We will call such measures $m$-empirical measures. In this case, when $N=2$, the existence of Monge solutions for any cost function $c$ is an easy consequence of the Birkhoff-von Neumann Theorem, although solutions to (1) are not unique in general. An immediate consequence is that the set of $m$-empirical measures is geodesically convex in Wasserstein space; that is, any two elements can be connected by a Wasserstein geodesic (often called a displacement interpolant) which lies in this set.

On the other hand, even for $m$-empirical measures, Monge solutions for $N\geq 3$ do not exist for some cost functions. Indeed, as exposed in [9], when $N\geq 3$, the convex polytope $\Pi(\mu_{1},...,\mu_{N})$ has extreme points which are not of Monge type, unlike in the $N=2$ case. This immediately implies the existence of cost functions for which Monge solutions do not exist, and [9] provides examples with relevance in physics for which this occurs. Intuition provided there, however, suggests that it is the repulsive nature of certain costs which leads to non-Monge optimizers for $m$-empirical measures, in agreement with known results in the continuous case. It remains reasonable to expect existence of Monge solutions for the quadratic cost function (2). It is similarly natural to conjecture that $m$-empirical marginals always have $m$-empirical Wasserstein barycenters (that is, that the set of $m$-empirical measures is barycentrically convex); we note that upper bounds on the size of the support of barycenters are known for general discrete measures [2], but the bound obtained there is $N(m-1)+1$ in the case of $m$-empirical marginals, much larger than $m$.

We exhibit here, by direct computation, an example showing that Monge solutions may not exist for $N\geq 3$ even for the quadratic cost. An immediate consequence is that the set of $m$-empirical measures is not barycentrically convex; there exist $m$-empirical marginals $\mu_{i}$ for which there does not exist a Wasserstein barycenter within the same set.

Our counterexample is for three measures ($N=3$) in two dimensions ($d=2$) supported on three points ($m=3$). These are the smallest values of these three parameters for which such counterexamples can exist. Indeed, for $N=2$, Monge solutions can always be found as discussed above. When $d=1$, optimal couplings are well known to be monotone increasing, which implies they are of Monge form and unique. Finally, we present here a simple proof that there always exists a Monge solution for any collection of $2$-empirical marginals, for any values of $d$ and $N$.

We define the set of $m$-empirical measures on $\mathbb{R}^{d}$ as $E_{m}:=\{\frac{1}{m}\sum_{i=1}^{m}\delta_{x_{i}}:x_{1},..,x_{m}\in\mathbb{R}^{d}\}$.

Here we present a counterexample to the existence of Monge solutions for $3$ marginals supported uniformly on $3$ points in $\mathbb{R}^{2}$.

We now present a simple proof that Monge solutions exist for $2$-empirical marginals.

The counterexample in Example 1 was found by brute force, through randomly generating many collections of empirical marginals and computing the solutions to (1). A couple of observations can be gleaned from the data obtained by this procedure:

1. (1)

   The occurrence of problems that do not have Monge solutions is quite rare; for three measures supported on three points in $\mathbb{R}^{2}$, we found that only about one in every $5000$ to $8000$ problems does not have a Monge solution. The frequency of these counterexamples seems to increase with the underlying dimension; we found that the failure of the Monge ansatz occurs more often in $\mathbb{R}^{3}$.

2. (2)

   Whenever the Monge ansatz fails, the difference between the minimal Monge cost and the actual optimal cost is quite small. We identified around $500$ cases when the Monge ansatz fails in $\mathbb{R}^{2}$; among these the greatest difference between the cost of the minimal Monge cost and the actual optimal cost was $4.3\%$. In fact, in most cases the error was much lower than the above upper bound as is shown in Figure 1.

The last observation suggest rigorously quantifying the error made by the Monge ansatz as an intriguing line of future research. It seems possible that the errors are small enough that the Monge ansatz as an approximation of (1) may still be a useful tool in some applications.