Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: + The paper makes good progress on an important problem. 
+ The algorithms are interesting and novel. 
- The experimental results are not so impressive.
clarity,_quality,_novelty_and_reproducibility: The algorithms in the paper combine known techniques but the end result is novel enough. 
summary_of_the_review: I recommend accepting the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

Similarly 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. 

strength_and_weaknesses: Strengths:
- 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. 
- The paper is quite well-written and easy to follow. 

Weaknesses:
- Many of the core ideas used are taken from prior work. However, the paper does seem to have technical depth on its own.


clarity,_quality,_novelty_and_reproducibility: The ideas are presented very clearly, and the paper is well-written. Previously known techniques are extended in a novel way. Experiments are performed on synthetic datasets and should be reproducible. 
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
strength_and_weaknesses: Strengths: Improves the (expected) additive error when the Wasserstein distance is smaller than $\epsilon/(d\log_{\sqrt{d}/\epsilon} 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.)~~

[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$.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written on its own. However, it does not present the existing techniques very clearly. As the paper states that it combines the existing techniques from the additive error algorithms and the relative error algorithms, it is not very clear to people who have not worked directly on the problem what the new innovation is and what the difficulty is to combine the techniques. It is thus difficult to assess the merits of the paper for someone who has not worked directly on the problem.

[Given the short review period, I have not been able to check the proofs carefully or read the proofs in the appendix.]

Minor points:
- Line 5 of abstract: add a comma after “dominates”
- Line 8: additive factor -> additive error (it’s additive and thus cannot be a factor)
- Section 1, paragraph 2, line 4: poly{...} -> poly(...). The same typo appears multiple times throughout the paper.
- Section 1, paragraph 2, line 5: there is no limiting process here, why “converge”?
- Section 1.1, paragraph 1, last line: change the semicolon to a comma
- Page 4, line -18: it is better to write $d = O(log_{1/\epsilon} n)$
- Page 4, line -7: “Since the spread…” This has never appeared before this point, it’s better to say that the algorithm guarantees the spread is …
- Page 4, line -7: the spread is $O(d/\epsilon)$, not exactly $d/\epsilon$, right? The same typo appears multiple times in the paper.
- Page 7, paragraph starting with “In the next section”: In the next section -> below (it’s still in the same section)
- Page 7, paragraph starting with “Quality of Approximation”: please fix “in this section”
- Page 8, paragraph starting with “Hierarchical Partitioning”, line 7: the footnote mark 4 is confusing, as it can be interpreted as the fourth power.
- Page 9, paragraph starting with “Datasets”, line 1: real data -> real-world data
- Page 9, paragraph starting with “Datasets”, line 7: add a comma before “which”
- Page 9, Figure 2: Colours are hard to distinguish when printed black & white. It’s better to use different line markers. 

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.~~

[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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this paper, the authors propose an approximation algorithm for the 1-Wasserstein distance between two discrete distributions up to an additive error. The proposed method is novel and all the reviewers are happy to accept the paper. So, I also vote for acceptance.

In the final version, please clearly discuss the connection of the proposed method with the recent work including "New streaming algorithms for high dimensional EMD and MST, STOC 2022 https://dl.acm.org/doi/abs/10.1145/3519935.3519979". 


justification_for_why_not_higher_score: Wasserstein distance approximation is a very important topic in ML and the paper proposes a new Wasserstein distance approximation algorithm. However, this paper has a bit narrower focus than the typical Wasserstein distance approximation and optimal transport problems. Thus, I recommend this for the spotlight paper.
justification_for_why_not_lower_score: This is an important work for 1-Wasserstein distance approximation.
Decision: Accept: notable-top-25%