On Computing Diverse Solutions in the Earth Movers Distance

Classically used for image retrieval tasks in computer vision, the Earth Movers Distance (EMD), also called the Wasserstein distance, has found numerous applications in natural language processing (NLP) and machine learning (ML). In NLP it is used as a measure of distance between sets of embeddings, and in ML it has been used to understand training dynamics, distributionally robust optimization, and many other tasks under active research. On the other hand, computing diverse solutions to optimization problems has also gained a lot of attention recently. In this DiverseX paradigm, one wants to develop algorithms that return a set of $r$ solutions that are maximally diverse; a common measure of diversity is the average or the minimum distance between the $r\choose{2}$ pairs of solutions. This paradigm is useful in generating more choices for the user, in fairness, and in robustness and security applications. In this work, we address the complexity of finding a diverse set of solutions in the EMD metric. Given an $n$ point metric space $(X,d)$ and integers $k \geq 1$ and $r \geq 2$, we consider the problem of computing $r$ many subsets of $X$, each of cardinality $k$, such that the minimum EMD between these sets is maximized. Motivated by applications from NLP, we also consider the problem of computing the farthest $k$-subset (from a given $k$-subset) in the EMD metric. On the lower bound side, we first show that assuming the Maximum-Span Hypothesis, it is W[1]-hard (with parameters $k$ and $r$) to obtain $k/(\log k)^{O(1)}$-approximation for non-metric cost functions, and W[1]-hard to obtain a $2-o(1)$ approximation for metric spaces. We also show that the problem restricted to the Euclidean setting with $\ell_2$ norm is W[1]-hard. Our first main algorithmic result is an $f(k, d, \varepsilon)n^{(O(1)}$ time $(1-\varepsilon)$ approximation algorithm for the $d$-dimensional Euclidean setting, which is tight in view of the above hardness results. Using different techniques, we also present a similar result for the farthest point problem in arbitrary metric spaces. Our second main algorithmic result is geared towards the search for polynomial time algorithms, where we present an $O(d)$ approximation for the Euclidean setting in $\text{poly}(n,k,d)$ time when $r=2$. Finally, we present $FPT(k)$ time, 2-approximate algorithms for arbitrary metric spaces when $r=2$. Since the class of problems we study requires to *find* diverse solutions in the EMD metric, our results use a combination of various geometric techniques that deviate from the techniques used to compute the EMD metric between a *given pair* of solutions, and may be of independent interest.