A Higher Precision Algorithm for Computing the $1$-Wasserstein Distance
Authors: Pankaj K Agarwal
Sharath Raghvendra
Pouyan Shirzadian
Rachita Sowle
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Wasserstein Distance
Earth Movers Distance
Bipartite Matching

Abstract: We consider the problem of computing the $1$-Wasserstein distance $\mathcal{W}(\mu,\nu)$ between two $d$-dimensional discrete distributions $\mu$ and $\nu$ whose support lie within the unit hypercube. There are several algorithms that estimate $\mathcal{W}(\mu,\nu)$ within an additive error of $\varepsilon$. However, when $\mathcal{W}(\mu,\nu)$ is small, the additive error $\varepsilon$ dominates, leading to noisy results. Consider any additive approximation algorithm with execution time $T(n,\varepsilon)$. We propose an algorithm that runs in $O(T(n,\varepsilon/d) \log n)$ time and boosts the accuracy of estimating $\mathcal{W}(\mu,\nu)$ from $\varepsilon$ to an expected additive error of $\min\{\varepsilon, (d\log_{\sqrt{d}/\varepsilon} n)\mathcal{W}(\mu,\nu)\}$. For the special case where every point in the support of $\mu$ and $\nu$ has a mass of $1/n$ (also called the Euclidean Bipartite Matching problem), we describe an algorithm to boost the accuracy of any additive approximation algorithm from $\varepsilon$ to an expected additive error of $\min\{\varepsilon, (d\log\log n)\mathcal{W}(\mu,\nu)\}$ in $O(T(n, \varepsilon/d)\log\log n)$ time. 

Published as a conference paper at ICLR 2023
A HIGHER PRECISION ALGORITHM FOR COMPUTING THE 1- WWWSSERSSENN DISTANCE
Pankaj K. Agarwal Sharath Raghvendra', Pouyan Shirzadian', and Rachita Sowle-
Duke University, ?Virginia Tech
ABSTRACT
We consider the problem of computing the 1-Wasserstein distance W(H, 2/) be- tween two d-dimensional discrete distributions μ and v whose support lie within the unit hypercube. There are several algorithms that estimate W), within an additive error of e. However, when W(u, v) is small, the additive error e dominates, leading to noisy results. Consider any additive approximation al- gorithm with execution time T En, We propose an algorithm that runs in (n, e/d) n) time and boosts the accuracy of estimating W(H, v) from e to an expected additive error of min (dloog m)) v) For the special case where every point in the support of μu and has a mass of 1/n (also called the Euclidean Bipartite Matching problem), we describe an algorithm to boost the accuracy of any additive approximation algorithm from E to an expected additive error of min(s, (d log log n W(H, 2)} in ((T s/d) log log n) time.
INTRODUCTION
Given two discrete probability distributions j and y whose support A and B, respectively, lie in- side the d-dimensional unit hypercube [0, 1] with max [A] [B]] W(n,v) (also called the Earth Mover's distance) between them is the minimum cost required to transport mass from v to under the Euclidean metric. The special case where |A| = |B] and the mass at each point of A U B is 1/n is called the Euclidean Bipartite Matching (EBM) problem. In machine learning applications, one can improve model μ. by using its Earth Mover's distance from a distribution y/ built on real data. Consequently, it has been extensively used in generative models (Deshpande al. (2018): Genevay al.] (2018); Salimans et al. (2018)) robust learning (Esfahani & Kuhn (2018)) supervised learning (Luise et al. (2018): Janati et al. (2019).
the 1-Wasserstein distance
and parameter estimation (Liu al. 2018); Bernton et al. (019)).
Computing the 1- I-Wasserstein distance between /ı and v can be modeled as a linear program and solved in On logn) time (Edmonds & Karp 1972); Orlin (1988)), which computationally ex- pensive. There has been substantial effort on designing E-addiive-approximatin algorithms that estimate W(H, 2) within an additive error of in n² vo"polydd log 1/e) time (Cuturi (2013); Lin lt al. (2019); Lahn et al. (2019)). When W(H, 2) is significantly smaller than E. however, the cost produced by such algorithms will be unreliable as it is dominated by the error parameter E.
To get a higher accuracy in this case, for > O, one can compute an a-relative approximation of the 1- I-Wasserstein distance, which is a cost w that satisfies W(n, v/) S w S aW(u,) v). There has been considerable effort designing relative-approximatio algorithms; however, many such methods suffer from curse of dimensionality;; i.e, their execution time grows exponentially in d. Furthermore, they rely fairly involved data structures that have good asympiotic execution times but are slow in practice and difficult to implement, making them impractical (Agarwal & Sharathkumar (2014); Fox & Lu (2020); Agarwal et al. (2022a ()). The only exception to this is classical greedy algo- rithm, based on a d-dimensional quadtree, that returns an O(d ( log n re)-relatvve approximation of the 1-Wasserstein distance in O(nd) time. It has been used in various machine-leariing and computer- vision applications (Gupta et al. 2010); Backurs et al. 2020 ). In the case of the Fuclidean Bipartite
"Following convention from Theoretical Computer Science, all authors ordered alphahetically.

---

Published as a conference paper at ICLR 2023
Matching, Agarwal & Varadarajan (004) and Indyk (2007) generalized the algorithm in the hierar- chical framework to achieve relative approximation ratio of Odd log(1/e)) in (n) time"
In this paper, we design an algorithm that combines any additive approximation algorithm with the hierarchical quad-tree based framework. As a result, our algorithm achieves better guarantees for both additive and relative approximations. To our knowledge, this is the first result that combines the power of additive and relative approximation techniques, leading to improvement in both settings.
1.1 PROBLEM DEFINITION
We are given two discrete distributions j and v. Let A and B be the points in the support of μ and v, respectively. For the distribution j (resp. f), suppose each point
A (resp. b E B) has probability of toa (resp. v)) associated with it, where Eue Pa = LLE B 2 = 1. Let G(A, B)
denote the complete bipartite graph where, for any pair of points E A and E B, there is an edge from a to b of cost ||a bll, i.e, the Euclidean distance between a and b.
For each point a A (resp. b E B), we assign a weight ny(a) = - (resp. n(bb = vn). We refer to any point v E A U B with a negative (resp. positive) weight as a demand point (resp. supply point) with a demand (resp. supply) of In(v)]. Given any subset of points V S AU B, the weight (V) is simply the sum of the weights of its points; i., m(V) = Evev 7(v). For any edge (a, 6) E A x B, let the cost of transporting a supply of B3 from to a be B'Ia - bll. In this problem, our goal is to transport all supplies from supply points to demand points the minimum cost. More formally, transport plan is a function a : A x B + 22 that assigns a non-negative value to each edge of G(A, B) indicating the quantity of supplies transported along the edge. The transport plan o is such that the total supplies transported into (resp. from) any demand (resp. supply) point E A (resp. b E B) is equal to -n((a) (resp. (b)). The cost of the transport plan Ø, denoted by w(aa), given by E(a,))EAB a(a, (aa - bll- The goal of this problem is to find a minimum-cost transport plan.
If two points E A and b E B are co-located (i.e, they share the same coordinates), then due to the metric property of the Euclidean distances, r)(b) = -vj(a), we can match the supplies to the demands at zero cost and remove the points from the input. Otherwise, if ry(b) * -n)(a). we replace the two points with a single point of weight 7aa) + (tb.. By definition, if the weight of the newly created point is negative (resp. positive), we consider it a demand (resp. supply) point. In our presentation, we always consider A and B to be the point sets obtained after replacing all the co- located points. Observe that, after removing the co-located points, the total supply U = (BB may be less than 1, However, it is easy to see that B)) (A] i.. the problem instance defined on AUB is balanced. We say that transport plan is an e-close transport plan if w() S W(u, v) sU.
In many applications, the distributions and v are continuous or large (possibly unknown) discrete distributions. In such cases, it might be computationally expensive or even impossible to compute W(a, 1/). Instead, one can draw two sets A and B of n samples each from j and v/, respectively. Each point a E A (resp. b E B) is assigned weight of r7(a) = 1/n (resp. ry(b) = 1/n). One can approximate the 1-Wasserstein distance between the distributions μ and v by simply solving the 1-Wasserstein problem defined on ((AAB), This special case where every point has the same demand and supply is called the Euclidean Bipartite Matching (EBM) problem. A matching M is set of vertex-disjoint edges in G(A, B) and has a cost 1/n E(,. bM [|u-b]] For the EBM problem. the optimal transport plan is simply a minimum-cost matching of cardinality n.
For any point set P in the Euclidean space, let Cmax(P) := (a ||a bll denote the distance of its farthest pair and Cmin (P) == ()
||a bll denote the distance of its closest pair. The spread of the point set. denoted by A(P), is the ratio A (P)) = Cuax (P)/Cmi (P)) When obvious from the context, we simply use Cmin Craxs and A denote the distance of its closest and farthest pair and its spread.
1.2 RELATED WORK
Relative Approximations: In fixed dimensional settings, i.e., d = O(1), there is exten- sive work on the design of near- near-lineat linear time Monte- Monte-Carlo (1 + E)-relative approximation al-
'0() hides poly(d, log n, 1/e) factors in the execution time.
2

---

Published as a conference paper at ICLR 2023
gorithms for 1- Wasserstten and EBM problems. The execution time of these algorithms (( (d log n ()) Khesin et al. (209 : Raghvendra & Agarwal (200 Fox & Lu 2220 Agarwal et al. (2022a). A recent algorithm presented by Agarwal et al. (2022b) improved the dependence on d slightly and achieved an execution time of (nn log log n n)) Nonetheless, the exponential
dependence on d makes it unsuitable for higher dimensions.
For higher dimensions, a quad-tree based greedy algorithm provides an expected (d n) approx- imation in ((nd) time. This algorithm constructs a randomly-shifted recursive partition of space by splitting each cell into 2d cells with half the side-length. For every cell of the quad-tree, the algorithm moves excess supply present inside its child meet any excess demand present inside an- other child. [Agarwal& & Varadarajan (2004) combined a different hierarchical partition with an exact solver to get an expected Of log L/E) aaaaapppoxiiaiion in (n+ time. Indyk (2007) combined the hierarchical greedy framework with importance sampling to estimate the cost of the Euclidean bipartite matching within a constant factor of the optimal. Additionally, there are ((d)) time algo-
rithms that approximate the matching cost with a factor of O(log" n) (Andoni et al. (2008); Chen
et al. ).
There are also approximation algorithms that run in Ó(n²) time; however, these algorithms rely on several black-box reductions and at present, there are usable implementations of these al- gorithms (Agarwal & Sharathkumar (2014); [Sherman] (2017)). The lack of fast exact and relative approximations that are also implementable have motivated machine-learning researchers to design additive-approxximatin algorithms, which we discuss next.
Additive Approximations: Cuturi (2013) introduced a regularized version of the optimal transport problem that produces an E-close transport plan, which can be solved using the Sinkhorn method. For input points within the unit hypercube, such an algorithm produces an e-close transport plan in O(n2//=²) time Fl Lin et al. (2019)) One can also adapt graph theoretic approaches including the algorithm by Gabow & Tarjan 1989 obtain an E-close solution in On Vd/e + (n/=²) time for points within the unit hypercube (Lahn et al. (2019)). Some of the additive approximation methods, including the Sinkhorn method, are highly parallelizable. For instance, the algorithm by Jambulapati
al. 2019) has a parallel depth of (L/E)) see also Altschuler et 2017 2019): Blanchet et al.
(2018) ; Quanrud| (2018); Dvurechensky et al. (2018); Guo et al. (2020)
1.3
OUR RESULTS
Let T(n,e) e) be the time taken by e-additive-approxxiatto algorithm input of n points in the unit hypercube. In Theorem I.I and 1.2] we present new algorithms that improve the accu- racy of any additive-pprrxximation algorithm for the 1-Wasserstein problem and the EBM problem, respectively.
Theorem 1.1. Given two discrete distributions i and v whose support lie in the d-dimensional unit hypercube and have spread n o1)), and a parameter > 0. a transport plan with an expected additive error of min(s, (d [olo n)W(p,v) } can be computed in (n, s/d) logvaje n) time; here, W(, v) is the 1- 1-Wasserstein distance between μ and
Theorem 1.2. Given two sets of n points A and B in the d-dimensional unit hypercube and param- eler e > O, a matching whose expected cost is within an additive error of min(e, (d log log n www of the optimal matching cost w* can be computed in O (/.ne//d) e/d) log log n) time with high probability.
Typical additive-approximaainn algorithms run in T'n, = Ö(n²) time and compute an E-close transport plan for any arbitrary cost function; i.e, they make no assumption about the distance be- tween points. The inputs to our algorithm, on the other hand, are point sets in the Euclidean space. Therefore, one can use an approximate dynamic nearest neighbor data structure to improve the ex- ecution time of such additive-approximatio algorithms. In particular, the algorithm by Lahn et al.) (2019) runs in O(1/s) pphses, where each phase executes one iteration of Gabow-Tarjan's is algo- nithm. As shown by Agarwal & Sharathkumar (2014), one can use /e approximaae dynamic nearest neighbor data structure with query/update time of O(n + d loggn) n) Andoni et al. (0144)
The execution time of Sinkhorn algorithm as well as other additive approximations depend on the diameter C' of the point set. In the case of d-dimensional unit hypercube, C = vd.
3

---

Published as a conference paper at ICLR 2023
to execute each iteration of Gabow-Tarjan's algorithm in O(n time. Combining with the algo- rithms from Theorem I.I and 1.2 we obtain the following relative- aatiivv-approiimatiinn algorithms. The details are provided in Appendix
Theorem 1.3. Let is and be two discrete distributions whose support lie in the d-dimensional unit hypercube and have polynomial spread, and ε > Q be a parameter. An transport plan under Euclidean metric can be computed in Oden time.
Theorem 1.4. Given two sets of points A and B the d-dimensional unit hypercube and parameter > O, O d_ log -approxximtt matching can be computed in O(dr log { time with high probability.
In contrast to our results, Agarwal & Varadarajan (2004) compute an Od log - matching in the same time. Therefore, our algorithm computes a more accurate matching for > VE For instance, consider the case where d vlog n. For any arbitrarily small constant e > 0,
the algorithm of Theorem 1.4 will run in ++n++5) time and return an O( OVVlog n) approxxxxmtto.n. In contrast, all previous methods that achieve sub-logarithmic approximation require 52(15/4) time
(Agarwal & Sharathkumar (2014)).
We also note that all of our algorithms extend to computing transport plans under any b metric in a straight forward way? For simplicity, we restrict our presentation only the Euclidean metric.
Overview of the algorithm: Our algorithm uses the hierarchical greedy paradigm. In our presenta- tion, we refer to a hypereube as cell. For any cell D, let Vn (A U B) n. Unlike quadtree based greedy algorithm, which splits each cell into 2d cells, we split it into min(/Val, {/))) cells. Thus, the height of the resulting tree T reduces from Ologgn to (llog n.). For any cell
I of T and any child C' of D. we move any excess supply or demand inside D' to its center. Let Ao (resp. B3) be set consisting of the center points of all children of O with excess demand (resp. supply). For any child to its center point in Ao (resp. Bn). Using additive-aprrxiimtton algorithm, (e/d)-close transport cost between Ag and Bn in T(VVol,e/d time. We report the sum of the transport costs computed at all cells of T an approximate 1-Wasserstein distance. This simple algorithm guarantees improvement in the quality the solutions produced by both additive and relatiee-aprroximation algorithms.
D with excess demand (resp. supply), we assign a weight of (Vor)
compute an
From the perspective of elative-appooximation algorithms, Agarwal & Varadarajan (2004) as well as Indyk (2007) have utilized similar hierarchical framework to design approximation algorithms. However, unlike our algorithm, they used an exact solver at each cell that takes Ω (I.A U Bu time. As result, to obtain quar-quadrttic execution time, they divided every cell into O 2/3) children, i.e., 1/e" S n²/3 3 or O(logı/e n). This also forces the height of the tree to be Oddoog1/e n), leading to an (d log1/= fa-ttto approximation. We replace the (2n²) time exact solver in their algorithm with T([Val,e) 0(VV)l²) time additive-approximation algo- rithm. Therefore, each instance (regardless of the number of non-empty children) can be solved in Ō(1V=l2) time. As a result, we are able to improve the approximation factor from (d log1/e n) to Oddlog n) and also remove restrictions on the dimension. Our algorithm now works for any dimension!
Technical Challenge: Using an additive-approximation algorithm at each cell increases the error that may be difficult bound. We use the following observation to overcome this challenge. In Section 2.2 we show that for any point set with spread A, an additive- aattiiv-approiiaatioonn algorithm can be used to compute 2-relative approximation in T(n, 1/A) time. The algorithu guarantees that the spread the point set at each cell is OddE)) and as a result, we get 2-relative approximation by using additiveeapproxxmaate
algorithm in OTT(n, e/d)) time.
Improvements for EBM: For the EBM problem, we obtain an improvement in the approxima- tion ratio, stated in Theorem 1.2 as follows: Instead of dividing each cell into fixed number
3 'The appendix is provided in the supplemental material. 'Owing to higher complexity of I.SH in arbitrary e, f--metrics, the approximation factor in Theorem 1.3 and i,4 slightly higher for arbitrary en-metrics.
4

---

Published as a conference paper at ICLR 2023
min(n, (4vd/E)") of children, we divide it into min n//2" children at each level i; here, level of any cell the tree is equal to the length of the path from the root to this cell. By doing so, we reduce the height of the tree to (log log... To analyze the running time, we show that the number of remaining unmatched points over all level i cells is Ö(n' (yn--z $). Since there are only sub-linearly many points remaining, we afford larger spread of O d ( and the resulting execution time of the additive approximation will continue to be O $) per level.
Open Question: Although our algorithms work in any dimension, we would like note that the relative approximation factor grows linearly in the dimension. Recently, Chen et al. (2022) removed the dependence on the dimension d from the approximation factor of quad-tree greedy algorithm by using a data dependent weight assignment. It is an open question if their approach can be adapted in our framework leading to a similar improvement in the approximation factor of our algorithms.
2 PRELIMINARIES
We begin by introducing few notations. For a cell D. we denote its side-length by &n and its center by cp. For a parameter f, let G E) denote grid that partitions O into smaller cells with side- length f. Recall that V- denotes the subset of A U B that lies inside D. We say that D is non-empty VO is non-empty. Recall that (VVo) = Evevo n(v). We define the weight of D to be r7V[) and
denote it by n()) We call a cell O deficit cell if vy(D) < 0, a surplus cell if vy(L) > 0, and neutral cell if (7)) O.
In this section, we provide simple transformation of the input for achieving an additive approxima- tion of the 1-Wasserstein distance. Furthermore, we show how an additiveapppooximatin algorithm for the I-Wasserstein problem can be used to obtain a (1 + r algorithm that runs in T/n, time, where A the spread of input points.
2.1 ADDITIVE APPROXIMATION IN EUCLIDEAN SPACE
For any E > O, given an additive apprxxiatan algorithm that runs in T(n, e) time, we present an algorithm compute E-close transport cost for distributions inside the d-dimensional unit hypercube U in (mmin[T(n, 5), n + T((2 (2v )d, {) time.
The algorithm works in two steps. In the first step, it constructs grid G = G(D', 2vd on the
unit hypercube D and computes transport plan 01 follows. For each non-empty neutral cell of G, σj arbitrarily transports all supplies to demands within the cell. Similarly, for any deficit (resp. surplus) cell, di arbitrarily transports supplies from (resp. to) all supply (resp. demand) points inside the cell to (resp. from) some arbitrary demand (resp. supply) points within the cell.
In the second step. the algorithm constructs a set of demand points A and a set of supply points B as follows: For any deficit cell O (resp. surplus cell D'), the point en (resp. cgr) is added to A (resp. B) with a weight of n[) (resp. v7())) Note that A Wasserstein problem. The algorithm computes --close transport plan 02 on the instance AUB in T(IA| + [B], e/2) time (See Figure IT) The algorithm returns w(a) + w((2) as an e-close transport cost on A AURI B.
a balanced instance for the 1-
We provide a discussion on the accuracy of the algorithm in Appendix A. The following lemma follows from the fact that [A|] + [B] is bounded by min(2n, (2vd/=)*).
Lemma 2.1. Given two point sets and B in the d-dimensional unit hypercube and a parameter > 0, an e-close transport cost can be computed in O(min[T $), + T((28
2 (2v8)dd {)) time.
Instead of transporting supplies inside cells arbitrarily, our algorithm in Section 3 recursively applies the same algorithm in each cell and obtains a higher accuracy.
2.2 RELATIVE APPROXIMATION FOR Low SPREAD POINT SETS
In this section, we show that an -additive-approxximati algorithm can be used to obtain a (1 (1++6 E)- relative-aprroximation algorithm for the 1-Wasserstein problem that runs in T(n, e/A time; here,
5

---

Published as a conference paper at ICLR 2023
(n)
(b)
Figure 1: (a) The algorithm transports supplies (red disks) demands (blue circles) within each cell and creates an instance by moving any excess supplies or demands to the center of the corresponding cells, (b) An e e/2-close transport plan is computed on the new problem instance.
A is the spread of the points in A U B. Since relative approximations are scale invariant, without loss of generality, we assume that the input has Cmax = 1 and Cmin = 1I/A.
Suppose (A) = +(B) = U. The minimum distance between any two points (a, E A B 1/4. Therefore, the cost of transporting a supply of is at least U/A We obtaín (1 + 8)- relative approximate transport plan by simply executing additive-approximaaie algorithm with an additive error of (EE/a in time s
Lemma 2.2. Given two point sets A and B in the d-dimensional unit hypercube with a spread of A, (I +) -approxmmmate transport plan can be computed in ' T time.
AN 7) PROBLEM
ALGORITHM FOR 1- WASSERSTEIN
In this section, we present our algorithm that satisfies the bounds presented in Theorem 1.1 We be- gin by defining hierarchical partitioning and a tree T associated with the hierarchical partitioning. Each node in T corresponds to non-empty cell in our hierarchical partition, and do not distin- guish between the two. We partition each cell of side-length i into [4vd/E]d cells of side-length most (s/4vō)e. We construct our hierarchical partition in randomly-shifted fashion follows.
Hierarchical Partitioning: First, we pick a point & uniformly at random from the unit hypercube [0, 1]d and set D = 1 Note that C is hypercube of side-length containing all points in A U B. We designate D* as the root of T. Let = [4vd/e]. For any cell D. if only one point of A U B lies inside D, we designate O as a leaf cell in T. For any non-leaf cell D. we construct its children by partitioning D using grid Gn G (n/k), into [4vd/e]* cells and create child node for each non-empty cell of this grid. We denote the set of children of a non-leaf cell D by CLUJ. Assuming the spread of A U B is 011), the height of T, denoted by h, is Olog 11).
Similar quadtrees, our hierarchical partitioning can seen a sequence of grids (Go, GI,..., (G)) where Go is the root and each grid G; refines the cells of grid G,-1. For each G, by &, Next, we describe our algorithm.
grid G, we denote the sell-side-lengee
Computing an approximate 1- I-Wasserstein distance: In this section, we present our algorithm for computing an approximate cost of an optimal transport plan on A B.
1 Creating instance at each cell: For each cell D of T, we create balanced instance Ig of the 1-Wasserstein problem as follows. If D leaf cell, then contains single point u of A J B, which we add to In. In addition, Otherwise, D is a non-leaf cell. For any child D' E C(U). if L' is a deficit or surplus cell, we add c with weight ((()) to In. The weight (y( represents the excess demands supplies of the points Vnr. Furthermore, we add the center point qn with a weight (n) to In- The instance In is balanced and has spread of Odde).
add the center point cn with weight -ry[D) to In-
Estimating the 1- L-Wasserstein distance: this step, for the root cell D", we compute an e/ /d-close transport plan ag- on Ig. Furthermore, for each cell O any level i > 0, using the

---

Published as a conference paper at ICLR 2023
algorithm from Lemma 2.2 compute a 2-approximate transport plan dn In. Our algorithm then reports the total cost of the transport plans computed at all cells of T, i.e w = Eoer w(on), as approximate 1- L-Wasserstein distance.
Retrieving an approximate transport plan: We retrieve an approximate transport plan o on the point set A U B by processing grids .G....., Go) in decreasing order of their level. First, for each non-empty cell D of G,, O is a leaf cell and Vo contains only one point. We map the only point in Va to cg. For some < h. assume (inductively) that after processing the non-empty cells of the grid G the following conditions (i)-iii hold for the current transport plan a within any cell D in G441: (i) if O is a neutral cell, then transports every supply to some demand point inside D. (ii) if O is a deficit (resp. surplus) cell, then a transports all supplies (resp. demands) inside O to (resp. from) some demand (resp. supply) point within D, and, (iii) if is deficit (resp. surplus) cell, the excess demand (resp. supply) is mapped to eo. Given this, we show how to process any non-empty cell 0 of G2 so that (ii- holds for D.
Recollect that on is a transport plan computed by our algorithm on In. By condition (ii), the excess supplies or demands at any child C' of D is mapped to cg', Therefore, for any pair of children D1, 02 E C[O], where 01 is surplus cell and Ol is a deficit cell, the transport plan transports or (Cm, Cm2) supplies from en, to 4n2- In addition, for any child 1 (resp. 02) of D, suppose D (resp. D2) is a surplus (resp. deficit) cell. If om(c,, cD) 0 (resp. on(c0, (D) > 0), then we map the supplies (resp. demands) from OO, (resp. (02) to co. It easy to confirm that after processing 0. (i)- holds for D. From triangle inequality, w(a) is upper-hounded by the total cost of the transport plans computed for each cell of T'; i.. w(o) S Ener w(ar).
Efficiency: For any i, let C; denote the set of non-empty cells of T level i. For each cell O E C. let nh be the number of points in Tu- Since the spread of the points in Ia is O(de)) executing the algorithm from Lemma 2.2 on I= takes (TTmo e/d) time (the same bound holds for the root cell as well). Since In contains at most one point for each non-empty child of D, AD S min (4vd/))²) Therefore, Enec, "0 S Enec. VVLl = n. Since T(n, 22(n), the running time of our algorithm on cells at level i is 0l T(mn.e/d) = edd)). Summing over all levels, the running time of our algorithm is O(T(n, e/d) log.///" n).
When the dimension is small constant, we get an improved running time as follows. For each level i of T, there are at most n non-empty cells at level and the instance created at each cell has a size of at most (4v)/E)4. Therefore, O(Enec, ((m,,e/ e/d)) = OnTI((AVd/e) ( ,/d)) = O(d)
and the overall running time will be improved to m( ((d)) log.a//"
Quality of Approximation: In this part, we analyze the approximate 1-Wasserstein distance com- puted by our algorithm. First, we show that the reported cost is E-close. For the root cell D", our algorithm computes an e/d-close transport plan on-. The remaining demands and supplies are recursively transported within the children of D', where each child has diameter e/2. Therefore, similar to Section 2. can argue that our algorithm reports an s-close 1-Wasserstein distance. Next, we show that the reported cost is an (ddlog.aje n) apparooxxnnnoo of the 1-Wasserstein dis- tance.
For each level < h, we show that the expected cost of the transport plans computed for all cells of level i is E Engc. w(ow)] = Odd)w(()) Here, a² is an optimal transport plan on A U B. C, denotes the set of non-empty cells of T at level i, and the expectation is over the choice of the random shift of the hierarchical partitioning. We bound E [Enec. w(on)] in two steps as follows. In the first step, we assign budget to every edge (a, b) with o (a, b) > 0 and show that the total budget assigned to all such edges is (in expectation) ((d)w(a"). In the second step, we redistribute this budget to the cells of level i in a way that the budget received by any cell D is at least w w(rr)/2 //2. Summing over all Ollog n) levels of T, the expected value of the total cost computed at all levels i < h is Oldlog.aa n))
Additionally, we show that the expected cost of mapping all points the centers of the cells of level h is (d Od n)w(("). Details of each step is provided in Appendix B. Theorem 1.1 follows from combining the two bounds.
7

---

Published as a conference paper at ICLR 2023
4 AN O(d n) -APAo)))AAPPPPPPAAAITAA ALGORITHM FOR EBM PROBLEM
Suppose A and B are two sets of points inside the d-dimensional unit hypercube, where each point a A (resp. E B) has a weight sy(a) = -1/mn (resp. r7(b) = 1/n). this section, we present an approximation algorithm for the EBM problem satisfying the bounds claimed in Theorem 1.2 Note that by invoking Lemma 2.1 on A U B, one can compute an E-close transport cost on A U B. To boost the accuracy of the algorithm of Lemma 2.1 in this section, we present Od log n.)- approximation algorithm for the EBM problem. To satisfy the bounds claimed in Theorem one can then report the minimum of the costs computed by the two algorithms.
Input transformation: We transform input points such that (1) all coordinates are positive in- tegers bounded by n(),, (2) an optimal matching on the transformed points is a (1 + E)- approximate matching with respect to the original points, and (3) the cost of the optimal match- ing is O log n/s). Similar transformations have been applied in several papers in the lit- erature (Agarwal et al. (2017); Lahn & Raghvendra (20TT). We describe this transformation in Appendix C.1. As before, can match and remove any co-located points a E A and b E B.
Next, assuming T(n,e) e) = O(n* poly(d, log n, log ))) for some 2 1, we describe our EBM algorithm. Our algorithm is easily adaptable to use any additive-approximatio
algorithm with a running time of T(n, e) = f log n, log 4)), where & 2 1 and t is a fixed constant.
Overview of the algorithm: Similar to Section 3 our HBM algorithm constructs hierarchical partitioning and the associated tree T, and executes the algorithm from Lemma 2.2 on the instance created for each cell o'. In contrast to Section 3 the tree ' constructed by EBM algorithm has height (log log rt), resulting in an improved approximation factor. The hierarchical partitioning of this section differs from the one in Section
B] in two ways. First, we partition the root cell into a grid G with cell-side-length of (dd//2 n logn/ n/s)) at the first level. The grid G may result in a high branching factor at the root; however, we show that, with probability at least 1 - =/Vd, no edges of an optimal matching will cross G1. Therefore, with that probability, all cells of G1 are neutral cells and the problem instance for the root is an empty instance; i.e, the branching factor of the root will not impact the running time of our algorithm. Second, for any cell D of level i, instead of splitting O into fixed number min min(n. (4vd/e)() of children, we divide O into min (n, nd/2') cells. Although this results in a spread of O(n2/2)) for the problem instance Ig, we show that the expected number of remaining unmatched points over all cells of level i is Ó(n1-1/2)). Therefore, the total execution time of our algorithm remains T(n, e/d) per level. These modifications result in a tree T of height Ollog log n.). We describe the details below.
Hierarchical Partitioning: Define 8 5d logg-lloog n. Similar Section we define cell O' as a randomly-shifted hypercube that contains all points of A U B and has a side-length of 2 max{Cmax: f1/=), where & = va vāōn. We designate O the root of T (O* is at level 0 of T). Define grid G == G(D", We add each non-empty cell of Gj to the tree as the children of O* We construct the hierarchical partitioning in a recursive fashion as follows. For any non-root cell D of T. if D contains only one point of A U B, then we designate D as a leaf cell. Otherwise, let D be a cell of level i. Define the grid GD = G GL), /2' ) and add the non-empty cells of Go to T as the children of D. For simplicity in presentation, we assume n 1/22 is an integer. For any cell O. denote the set of children of D in T by C(D). The height of T, denoted by h, is Ollog log.).
Similar to Section 3 our hierarchical partitioning is also a sequence of grids (Go, Gr,...,GiA GR), v 8n, and for each 2 < i S h, the where Go is the root cell D" G1 has cell-side-length of e é cell-side-length of G, is L, = ön 1/2"1
Computing approximate matching cost: To estimate the matching cost, similar to Section 3 our algorithm creates an instance of the 1-Wasserstein problem for each cell of the tree T. Using the algorithm from Lemma 2.2] our algorithm computes a 2-approximate transport plan for the instance created for each cell and returns the total cost of such transport plans as an approximate matching cost. This completes the description of the algorithm.
We describe the details of retrieving a matching in Appendix C.2, the quality of approximation in Appendix C.3, and the efficiency of our algorithm in Appendix C.4.
8

---

Published as a conference paper at ICLR 2023
garden
sestiee aganth
1M0
Liissarsoe
1000
100
(a) 15D: time
(b) Real: time
(c) 15D: time
(d) Real: time
aggettin
parthe
Louste thi Mpr
Peseertee ne
lgertin
084
TH 150 Die
26
Mip Do0 200
(c) 155:: cost
(f) 15D: n time
(g) Real: n cost
(h) Real: time
Figure 2: (a) and (b) Comparison with the Sinkhorn algorithm, (c) and (d) Comparison with the LMR algorithm, and (e)-(h Comparison with the Addietric-Additiee algorithm
EXPERIMENTS
In this section, we conduct experiments to show that our algorithms from Section 3 and Section improve the accuracy of the additive approximation algorithms. We test implementation of our algorithm, written in Python, on discrete probability distributions derived from real-world and syn- thetic data sets. All tests executed computer with 2.50 GHz Intel Core i7 processor and 8GB of RAM using a single computation thread.
sets of n samples taken from synthetic (distribution) and real-world data sets. For each dataset, we use our algorithms to compute the minimum-cos match- ing between these samples and present our results averaged over 10 executions. To generate the synthetic data, we sample from a uniform distribution inside a a 2-dimensional unit square placed on random plane in 15-dimensional space (15D). For real-world dataset, we use the Adult Census Data (UCI repository), which is point cloud in IR with continuous features for 35, 000 individuals, divided into two categories by income (Dua & Graff (2017). See Appendix E for the results of our experiments on additional datasets.
Datasets: We test our algorithms
In our first experiment, we compare our algorithm with existing additive approximation schemes, namely the Sinkhorn method (Cuturi (2013) (resp. LMR algorithm (Lahn et al. (2019)). We use the Sinkhorn (resp. LMR) algorithm as a black-box within our algorithm from Section (1- [--Waseerteenn algorithm) and compare its execution time with the standard Sinkhorn (resp. LMR) implementation. We set the parameters of the Sinkhorn and LMR algorithms in such a way that the error produced by them matches with the error produced by 1-Wasserstein algorithm. As shown in Figure 2 (a)-(d), our algorithm runs significantly faster than both the Sinkhorn and the LMR algorithms while producing solutions of similar quality. In our second experiment, we also compare the accuracy as well as the computation time of our algorithms (I-Wasserstein algorithm and our EBM algorithm from Section 4) with the additive approximation algorithm from Section 2.1 (Geometric-Additiv algorithm). For this experiment, our algorithms use the Sinkhorn algorithm as black-box. The results of this experiment are shown in Figure (h). We observe that our algorithms achieves a better accuracy (see Figure 2 (a) and (c)), especially real-world data sets. As expected, the execution time of our algorithms increase slightly (see Figure 2 (d)). Furthermore, we observe that as the sample size increases, the costs returned by algorithms converge to the optimal cost, whereas the Geometric-Addiite
Results:
Approximation based approach does not.
Finally, we highlight the scalability of our algorithms. For input of 3 million points drawn from a 2 dimensional uniform distribution on the unit square, our 1- W-sasserstein algorithm runs in 593 seconds and computes approximate transport cost of 0.0093. Furthermore, for input of 1.5 million points for the 15D dataset, our 1-Wasserstein algorithm computes an approximate cost of 0.0304 in 608 seconds.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
We would like to acknowledge. Advanced Research Computing (ARC) at Virginia Tech, which provided with the computational resources used to run the experiments. Research presented in this paper was funded by NSF grants CCF-1909171, CCF-2223871, IIS-18 AS--814493, CCF-2007556, and CCF-2223870. We would like to thank the anonymous reviewers for their useful feedback.
REFERENCES
Pankaj K. Agarwal and R. Sharathkumar. Approximation algorithms for bipartite matching with metric and geometric costs. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 555-564, 2014.
Pankaj K. Agarwal and Kasturi R. Varadarajan. A near-linear constant-factor approximation for Euclidean bipartite matching? In Proceedings of the 20th annual symposium on Computational geometry, pp. 247-252, 2004.
Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster algorithms for the geometric transportation problem. In Proc. 33rd International Symposium on Computational Geometry, pp. 7:1-7:16, 2017.
Pankaj K Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao. Deterministic, near- linear E-approximation algorithm for geometric bipartite matching. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1052-1065, 2022a.
Pankaj Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. An improved E-approximation algorithm for geometric bipartite matching. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Schloss Dagssuh-Lccibniz-ZZentunn für Infor-
matik, 2022b.
Jason Altschuler, Jonathan Niles-Weed and Philippe Rigollet. Near-linear time approximation gorithms for optimal transport via sinkhorn iteration. Advances in neural information processing systems, 30, 2017.
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles-Weed. Massively scalable sinkhorn distances via the nyström method. Advances in neural information processing systems, 32, 2019.
Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high- dimensional spaces. In SODA, volume 8, pp. 343-352, 2008
Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms,, pp. 1018-1028 SIAM, 2014.
Arturs Backurs, Yihe Dong. Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Scalable nearest neigh- bor search for optimal transport. In International Conference on Machine Learning, pp. 497-506, 2020.
Espen Bernton, Pierre E. Jacob, Mathieu Gerber, and Christian Robert. On parameter estimation with the wasserstein distance. Information and Inference: A Journal of the IMA, 8(4):657-676, 2019.
Jose Blanchet, Arun Jambulapati, Carson Kent, and Aaron Sidford. Towards optimal running times for optimal transport. arXiv preprint arXiv: 1810007711 2018.
Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional emd and mst. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 222-233, 2022.
Marco Cuturi. Sinkhom distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems 26, pp. 2292-2300, 2013.
10

---

Published as a conference paper at ICLR 2023
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing. Generative modeling using the sliced wasserstein distance. In Proceedings of the IEEE conference on computer vision and pattrrn recognition, pp. 3483-3491 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt::t/acchhhiiie ics. uci. edu/ml
Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport:
Complexity by accelerated gradient descent is better than by sinkhorn's 's algorithm. In Interna- tional conference machine learning, pp. 1367-1376. PMLR, 2018.
Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248 264, 1972.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115-66) 2018.
Kyle Fox and Jiashuai Lu. A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread. In Proc. 36th Annual Symposium on Computational Geometry, pp. 145188, 2020.
H. N. Gabow and R.E. Tarjan. Faster scaling algorithms for network problems. SIAM J. Comput., 18: acm. October 1989. ISSN 0097-5397. doi: 10.1137/0218069 URL http://porttll. wttp::m.cmmmmmmmmmmmmmmdd 75806
Aude Genevay, Gabriel Peyre, and Marco Cuturi. Learning generative models with sinkhorn di- vergences. In International Conference on Artificial Intelligence and Statistics, pp. 1608-1617, 2018.
Wenshuo Guo, Nhat Ho, and Michael Jordan. Fast algorithms for computational optimal transport and wasserstein barycenter. In International Conference on Artificial Intelligence and Statistics, pp. 2088-2097, 2020.
Rishi Gupta, Piotr Indyk, and Eric Price. Sparse recovery for earth mover distance. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1742- 1744. IEEE, 2010.
P. Indyk. A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In Proceedings of the 18th Annual ACM-SIAM Symposium Discrete Algorithms, pp- 39-42, 2007.
Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct Ô(1/e) iteration parallel algorithm for optimal transport. arXiv preprint arXiv: (0600/906.00668, 2019.
Hicham Janati, Marco Cuturi, and Alexandre Gramfort. Wasserstein regularization for sparse multi- task regression. In The 22nd International Conference on Arlificial Intelligence and Statistics, pp. 1407-1416. PMLR, 2019.
Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. Preconditioning for the geo- metric transportation problem. arXiv preprint arXiv:1902.08338 2019.
Nathaniel Lahn and Sharath Raghvendra. A faster algorithm for minimum-cost bipartite matching in minor-free graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 569-588. SIAM, 2019.
Nathaniel Lahn and Sharath Raghvendra. An 5/4) time E-approximation algorithm for RMS matching plane. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pp. 869-888, 2021.
Nathaniel Lahn, Deepika Mulchandani, and Sharath Raghvendra. A graph theoretic additive ap- proximation of optimal transport. In Advances in Neural Information Processing Systems 32, pp- 13813-13823, 2019.
11

---

Published as a conference paper at ICLR 2023
Tianyi Lin, Nhat Ho, and Michael 1. Jordan. On the efficiency of the sinkhorn and greenkhorn algorithms and their acceleration for optimal transport. arXiv preprint arXiv:1906.01337, 2019.
Huidong Liu, G. U. Xianfeng. and Dimitris Samaras. A two-step computation of the exact gan wasserstein distance. In International Conference on Machine Learning, pp. 3159-3168, 2018.
Giulia Luise, Alessandro Rudi, Massimiliano Pontil, and Carlo Ciliberto. Differential properties of sinkhorn approximation for learning with wasserstein distance. Advances in Neural Information Processing Systems, 31, 2018.
James Orlin. A faster strongly polynomial minimum cost flow algorithm. Proceedings of the Twentieth anmual ACM symposium on Theory of Computing, pp. 377-387, 1988.
Kent Quanrud. Approximating optimal transport with linear programs. arXiv preprint
arXiv.1810.05957. 2018.
Sharath Raghvendra and Pankaj K. Agarwal. A near-linear time e-approximation algorithm for geometric bipartite matching. J. ACM, 670))18:1-18:1, 2020. doi: 10.1145/3393694. URL
https://doi //0 1e11111433338
Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving gans using optimal transport. In International Conference on Learning Representations, 2018.
Jonah Sherman. Generalized preconditioning and undirected minimum-com flow. In Proceedings of
the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 772-780, 2017.
12


Reviews:
[{"review_id": "Ce9W2Zcrx2O", "reviewer": "Reviewer_4W22", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers approximating the 1-Wasserstein distance between two discrete distributions up to an additive error. Suppose that $\\mu$ and $\\nu$ are two discrete distributions contained within the unit hypercube. Both are supported on n points and both have a $\\operatorname{poly}(n)$ spread. The paper shows a randomised algorithm approximating the 1-Wasserstein distance $W_1(\\mu,\\nu)$ up to an expected additive error of $\\min\\\\{\\epsilon, (d\\log_{\\sqrt{d}/\\epsilon} n)W_1(\\mu,\\nu) \\\\}$ in $O(T(n,\\epsilon/d)\\log_{\\sqrt{d}/\\epsilon} n)$ time, where $T(n,\\epsilon)$ is the time taken by an $\\epsilon$-additive approximation algorithm. Based on this core result, the paper also obtains relative-error algorithms for the Euclidean bipartite matching problem. ", "summary_of_the_review": "This is a solid paper on its own. ~~but it is difficult to evaluate the novelty in the techniques as the paper is not clear on this aspect. The guarantee on expected additive error is not enticing, either.~~\n\n[Update] The techniques are mostly based on the existing ones but it is nontrivial to combine them with small twists in various places. I would recommend acceptance though it looks more like an ESA paper instead of an ICLR paper.", "strength_and_weaknesses": "Strengths: Improves the (expected) additive error when the Wasserstein distance is smaller than $\\epsilon/(d\\log_{\\sqrt{d}/\\epsilon} n)$.\n\n~~Weaknesses: The main weakness to me is that the guarantee is in the expected additive error, not a worst-case error guarantee. (The abstract should also state that it’s the “expected” additive error clearly.)~~\n\n[Update] The authors have clarified that repeating $O(\\log(1/\\delta))$ times gives a worst-error guarantee of the same magnitude with probability at least $1-\\delta$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5OMVRPjmR0", "reviewer": "Reviewer_8UAQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper gives a new algorithm for computing the Earth Mover's Distance between two discrete distributions in the hypercube. This is an extensively studied problem with several theoretical algorithms papers studying it. This present paper exploits some of their efficient-in-practice techniques in order to design a practical algorithm.", "summary_of_the_review": "I recommend accepting the paper. ", "strength_and_weaknesses": "+ The paper makes good progress on an important problem. \n+ The algorithms are interesting and novel. \n- The experimental results are not so impressive.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "3WjEc4XuXf", "reviewer": "Reviewer_LSEt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors consider the problem of computing the 1-Wasserstein distance (Earth Mover’s distance) between two d-dimensional discrete distributions $\\nu$ and $\\mu$. In this problem the mass distributed over a set of supply nodes according to distribution $\\nu$, needs to be transported and distributed to the demand nodes in $\\mu$. The amount of mass supplied or demanded by each node is given and the per unit transportation cost between a pair of nodes is proportional to the $\\ell_2$ (Euclidean) distance between the nodes. The goal is to compute the minimum cost required to transport the mass from the supply nodes to demand nodes. A special case of this problem where all nodes have the same amount of demanded or supplied mass, is also considered. This problem is called Euclidean Bipartite Matching (EBM), since in the optimal solution a demand node will be connected to a single supply node and vice versa. While prior work on this problem had provided both additive and relative approximation guarantees, the contribution of this paper is an algorithm that combines the two types of guarantees. Specifically, for the Earth Mover’s distance problem, the error is the minimum between $\\varepsilon$ and $(d\\log_{\\sqrt{d}/\\varepsilon}n) \\mathcal{W}(\\mu,\\nu)$, where $\\mathcal{W}(\\mu,\\nu)$ is the optimal cost. The second term provides an improved relative approximation compared to $d\\log n$ achieved in prior work, while the additive error is bounded by $\\varepsilon$ at the same time. \n\nSimilarly to prior work, the algorithm uses a randomly shifted hierarchical partitioning of the space recursively subdividing cells with multiple points in them. The algorithm first tries to satisfy the demands using the supply from the same cell of the partitioning and this is also done in a recursive manner, therefore starting from the lower levels of the hierarchical tree and moving up. When a particular cell has more supply than demand (or vice versa), the remainder is moved to its center to be handled by a higher level cell. This paper differentiates from prior work on relative approximation algorithms by using exact solvers for each cell, whereas faster approximate solvers are used in this paper leading to smaller cell size and better approximation guarantees. For the problem of Euclidean Bipartite Matching (EBM), the authors exploit the fact that cells in the hierarchical tree are more likely to be balanced (in terms of internal supply and demand) and they are able to improve the relative approximation to $d\\log log n$, while maintaining the additive approximation. \n", "summary_of_the_review": "I believe this paper makes a solid contribution by providing improved additive and relative approximation guarantees with a single algorithm for a well-known problem. ", "strength_and_weaknesses": "Strengths:\n- This paper makes an improvement on an important problem and at the same time gives both an additive and relative approximation guarantee, which could make the algorithm even more widely applicable. \n- The paper is quite well-written and easy to follow. \n\nWeaknesses:\n- Many of the core ideas used are taken from prior work. However, the paper does seem to have technical depth on its own.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%