- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
In this paper, the authors present new practical techniques for scaling up the computation of semi-discrete optimal transport plans. The first is a preprocessing of the target points into a layered network that groups similar points together. Then, the authors use this preprocessing in a hierarchical sequence of semi-discrete optimal transport solutions, where the solution to layer and the connections to layer are used to warmstart the initial solution to the computed larger solution in layer . The authors show experimentally that this layered structure and warmstarting sequence significantly improves the runtime of computing semi-discrete optimal transport plans.
Critical strengths
I really enjoyed reading this paper. There was a clear issue with existing work on semi-discrete optimal transport solvers: variational methods for semi-discrete optimal transport can still require many iterations, and each iteration can still require comparing each sample point to its candidate cell centers. The authors propose a cute solution to this problem, imposing a data structure similar to the hierarchical navigable small world framework to initialize weights of nearby points similarly and speed up assignment of sample points to corresponding cell centers. Experimentally, this cute solution leads to a significant improvement in runtimes. Overall, the paper was pretty well written and quite easy to follow.
Critical weaknesses
My only issue would be that there is a chance the impact of their results is small. I found that their discussion of related work was also a bit bare, mostly restricted to existing variational methods for semi-discrete optimal transport. A more detailed comparison with other existing work may remove this concern, however. Without just saying "related work is weak", I wanted to give some thoughts on other potentially useful works to compare against.
Nearest neighbor search: (useful when assigning samples to their respective cells)
- Classical algorithms for nearest neighbor search suffer from the curse of dimensionality, in the worst case attaining space ("Geometric approximation algorithms" by Har-Peled is a great initial reference)
- Modern nearest neighbor search designed to mitigate the curse of dimensionality follows the hierarchical navigable small world framework, which is very similar to the preprocessing step performed by the authors ("Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs" by Malkov and Yashunin)
Other semi-discrete optimal transport solvers:
- The authors refer to "conventional numerical solvers" but give no citations. Is this in reference to first-order optimization over the power cell assignments (e.g. "Minkowski-type theorems and least-squares clustering" by Aurenhammer et al. and/or "Notions of optimal transport theory and how to implement them on a computer" by Levy and Schwindt)?
- The work described by the authors is not the first to avoid comparing all sample-to-target pairs! A comparison against other geometric preprocessing algorithms would be useful. Some such references include:
- "Approximating the Earth Mover's Distance between sets of geometric objects" by van Kreveld et al.
- "A combinatorial algorithm for the semi-discrete optimal transport problem" by Agarwal et al.
Questions for authors
- See the weaknesses above. How does your layered approach compare to (1) the hierarchical navigable small world framework, and (2) the geometric preprocessing algorithms for semi-discrete optimal transport?