Solving (partial) unbalanced optimal transport via transform coefficients and beyond

Weaknesses:

• Many results of this paper are either marginal derivations of past works or duplicated results. For example, Corollary 4 is a weaker result of Theorem 13 in [1] where the former only has asymptotic convergence. At the same time, the latter provides a non-asymptotic convergence rate in terms of tau. I believe that even for PUOT obtaining the convergence rate in terms of tau would not be too difficult.
• While CROT indeed yields sparsity compared to an entropic-regularized transport plan, an $\ell_2$-regularized transport plan would also induce sparsity while giving an accelerated convergence rate.
• There is no complexity analysis for algorithm 1. Judging by the numerical experiments, I believe that the proposed method will be slower than the entropic-regularized Sinkhorn (which is expected since the entropic regularization induces acceleration) or the gradient extrapolation method in [1].
• The theoretical contribution is quite limited, as the authors only use KKT conditions to derive the transform coefficients.

References [1] "On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error". Quang Minh Nguyen, Hoang Huy Nguyen, Lam Minh Nguyen, Yi Zhou

1. The literature review and thus positioning of this work's contribution is very insufficient. Please cite the relevant work as mentioned below and properly re-write the relevant literature discussion. E.g:

• "Previous researches always add entropy regularization term for solving OT, UOT and PUOT. " --> See [1] for UOT and [2] for OT both with l2-regularization.
• "As we already have abundant methods available for tackling OT problems, the idea of converting UOT to OT brings us a brand new perspective in dealing with UOT." --> Results like this were done in the literature, where [1] showed tight bounds on how fast UOT converges to OT with the growth of $\tau$. So this is not the first work.

2. This paper lacks mathematical rigor in the formulation and development of the methods. The idea is presented in a very heuristic form.

• Proposition 1 is given using the notion of "transformed pairwise distance" that is never properly introduced in the paper. Maybe solving the optimal "transformed pairwise distance" might correspond to solving the original UOT problem, thereby invalidating the whole purpose of this paper. Other results are also very informal.
• Following up the above comment, the Algo 1 in the paper runs iteratively to adjust the "transformed pairwise distance" (I know it's $s_{ij}$, but it is equivalent way of saying), but we can't know how long it should run to converge.
• Following up the above comment, you in fact do not equivalently yet approximately convert the UOT/PUOT problem into OT. Moreover, we cannot know how good such approximate conversion is. So your whole framework and idea, though interesting, are invalid. Please note that even if you use OT solver to solve your converted OT problem, how would you next retrieve your UOT solution out of that because your equivalence is approximate in the first place?

3. Experiments are on synthetic data only, and thus are very weak.

[1] Nguyen, Quang Minh, Hoang Hai Nguyen, Yi Zhou and Lam M. Nguyen. “On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error.” (2022). [2] Essid, Montacer and Justin M. Solomon. “Quadratically-Regularized Optimal Transport on Graphs.” SIAM J. Sci. Comput. 40 (2017): A1961-A1986.

1. All the results presented in the paper are not associated with rigorous theoretical guarantee, which makes the results less reliable.

2. There are many claims without justification in the paper. For instance, in the paragraph above Proposition 3, the authors claimed that the solution $\boldsymbol{\pi^*}$ should be sparse in most cases without any explanations and citing relevant papers.

3. The name of partial unbalanced optimal transport is confusing. In the literature [1], this problem is referred to as semi-constrained optimal transport. On the other hand, when talking about partial transportation, ones think about the problem of transporting a fraction of the mass as cheaply as possible consdiered in [2, 3].

4. The writing of the paper is not good. There are many undefined notations (e.g. KL divergence, $\widehat{C}^*_{i,j}$ in Proposition 1), grammatical errors as well as typos (see Question section). Furthermore, the authors also need to cite more relevant papers.

References

[1] Khang Le, Huy Nguyen, Quang Nguyen, Tung Pham, Hung Bui, Nhat Ho. On Robust Optimal Transport: Computational Complexity and Barycenter Computation. In NeurIPS, 2021.

[2] Laetitia Chapel, Mokhtar Z. Alaya, Gilles Gasso. Partial Optimal Transport with Applications on Positive-Unlabeled Learning. In NeurIPS, 2020.

[3] Khang Le, Huy Nguyen, Tung Pham, Nhat Ho. On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity. In AISTATS, 2022.

• Convergence guarantees of Algorithm 1 are not exposed. The used convergence criterion should be stated and should be related to the derived KKT conditions. The same remark holds for PUOT related algorithm.
• Formal proofs or elements of proof of the theoretical results on which CROT algorithm is based are not proposed. Also theoretical guarantees on the discrepancy between the estimated $\pi^*$ by CROT and the true coupling matrix corresponding to the UOT are not provided.
• The motivation of solving the reweighted OT using Sinkhorn, OT with L2-norm or sparse OT algorithm is a bit hazy. Moreover those solvers necessitate hyper-parameters that are not easy to tune. As such the obtained coupling matrix $\pi$ may highly differ from the one that can be achieved while solving directly the UOT/PUOT problem using existing methods.
• The reported empirical evaluations are not always convincing. For instance, when assessing the quality of $\pi^*$ by CROT, the distance $\sum_{ij} |\pi^*_{ij} - \pi^o_{ij}|$ where $\pi^o$ is the solution of a plain OT (according to my understanding) computed by network-flow algorithm. It would be fair and meaningful to contrast $\pi^*$ with the coupling matrix given by existing UOT or PUOT solvers. Another example is Figure 4 which illustrates $\pi^*$ on a UOT problem with $\tau=10^5$. Such setting will enforce the marginal constraints to be met, leading to a coupling solution close to OT. Therefore, it is unclear why Figure 4 does consider Sinkhorn instead of non-regularized OT.
• In the domain adaptation task, Table 1 does not consider JUMBOT coupled with UOT solved by existing methods in order to provide a fair evaluation and assess the benefit of CROT over existing UOT solvers on this specific application.
• Authors should proof read the paper for some inconsistent text formulations.

• This subject has been explored in greater generality (e.g. in Chizat et al. 2018) and algorithms for computing unbalanced optimal transport have already been proposed and used. The unique contribution here is that the resulting transport map is sparse. However, the benefit of that is not clear to me.
• There is no analysis of the convergence speed of Algorithm 1.
• The approach seems to scale poorly and accordingly the experimental data sets are all very small. The iterations of Algorithm 1 are O(NM), as expensive as Sinkhorn iterations, and that's before the main step of solving the OT problem.
• The text needs to be thoroughly copy-edited as it contains numerous errors. e.g. "it does not match most of situations", "for avoid heavy computations", "if s_i,j is much approaches to 0", etc.
• The text in the figures in tiny. Figure 3 is unreadable when printing in black&white.