NeurIPS 2020

Fast Unbalanced Optimal Transport on a Tree


Meta Review

Reviewers are marginally enthusiastic about this paper, which proposed a data tree-structure to simplify the solution to the original OT problem. In addition to the various issues reviewers raised, there are additional criticisms which the authors should consider in their revision. 1. An important relevant paper is not cited: https://papers.nips.cc/paper/6566-stochastic-optimization-for-large-scale-optimal-transport.pdf 2. The contributions include: (1) propose the tree-like structure to solve the unbalanced OT problem (which include standard OT as the special case) (2) prove that their time complexity is O(nlog^2n). However, the paper did not say anything about the accuracy, other than some experiments. The existing OT solvers needs O(n^2/\eps) complexity, where \eps is the additive error. The cost of OT is roughly on the order of n^2. Therefore, it is probably affordable to use \eps = \eps' n^2, which makes the complexity become O(1/\eps') , where \eps' is the relative error. In their experiments, the relative error is about 0.05, which is fairly easy to achieve using existing OT solver.