- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper aims to introduce a low-rank formulation of the multimarginal optimal transport (MOT) problem. Its main contributions include constructing two low-rank formulations based on Tucker and CP decompositions and establishing theoretical approximation bounds between the proposed formulations and the original MOT problem. For a particular class of cost functions, the authors further exploit the properties of CP decomposition to formulate explicit CPMOT (ECPMOT), a more tractable variant of CPMOT, and derive a theoretical bound on the difference between their optimal objective values. Based on these formulations, the authors propose three algorithms: two mirror descent methods for TuckerMOT and CPMOT, respectively, and an alternating minimization method for ECPMOT. The experiments demonstrate substantial improvements in computational efficiency and suggest that the latent structures induced by the low-rank decompositions have meaningful geometric interpretations.
The paper introduces a complex low-rank MOT problem and provides extensive theoretical analysis and effective solution algorithms. As a theoretical contribution, the work is relatively comprehensive and deserves recognition. However, although the authors establish approximation bounds between the proposed formulations and the original MOT problem, these bounds are rather loose and do not establish convergence to the solution of the original MOT problem in an appropriate limiting regime. Therefore, unlike entropic regularization, which is commonly used to accelerate the computation of OT, the proposed formulation should not simply be viewed as a computational improvement over the original MOT problem, but rather as a distinct OT problem with explicit rank constraints. However, the authors do not sufficiently discuss why such constraints should be imposed, what motivates their introduction, or whether they are relevant to practical applications. Therefore, I believe that the main weakness of this work is the lack of a convincing practical motivation for the proposed problem, despite the solid theoretical results established for the given formulation.
Critical strengths
The mathematical derivations are rigorous and well-developed. The authors provide a thorough analysis of the proposed complex problem, and the algorithms are well-designed and appropriate.
Critical weaknesses
-
The paper does not clearly explain the practical purpose of the proposed formulation. Although multimarginal optimal transport (MOT) has established applications, the practical relevance of imposing additional low-rank constraints is not adequately discussed. While the authors theoretically establish approximation bounds between the low-rank formulations and the original MOT problem, these bounds are extremely loose and provide limited guidance for practical applications. Therefore, the proposed low-rank formulations cannot be regarded as computational approximations of the original MOT problem in the same sense as entropic regularization, since the paper does not establish any relevant convergence guarantees. Although the authors mention in the appendix that the approximation error in a particular example is much smaller than the theoretical upper bound suggests, this single example does not guarantee that the approximation error is generally small. Moreover, it seems plausible that counterexamples with substantially larger approximation errors could be constructed. Therefore, the proposed formulation cannot be regarded as a well-justified approximation of the original MOT problem. At the same time, the authors do not identify potential practical applications that would motivate studying this new rank-constrained problem in its own right. I consider this lack of motivation to be the most significant weakness of the paper.
-
Although the second experiment in the main text and Experiment 4 in Appendix B.1 suggest that the latent space structures induced by the proposed methods may have meaningful geometric interpretations, the paper does not sufficiently investigate this aspect. In particular, both theoretical analysis and more extensive experimental evidence are needed to support these observations.
Questions for authors
-
Could the authors provide further clarification on the motivation behind the proposed model?
-
Could the authors provide an analysis of failure cases?
-
Could the authors further validate the proposed methods on real-world datasets?
Response to Reviewer dLpn
We thank Reviewer
dLpnfor their constructive feedback. In this comment, we specifically address Question 2 regarding failure cases. For our responses to the other questions and concerns, please refer to the general response.Consider the setting where a(1)=⋯=a(d). In this case, the optimal transport tensor is given by T⋆=diag(n1,…,n1) and satisfies rankCP+(T⋆)=n. The optimal transport cost is therefore 0. In this setting, with n=20 support points, d=4 marginals, and ε=0.005, the Sinkhorn algorithm achieves a transport cost of 6.4×10−3, while eCPMOT obtains the following transport costs: