acceptodds
Under review as a conference paper at ICLR 2027

Low-Rank Multimarginal Optimal Transport

Abstract

Multimarginal Optimal Transport (MOT) suffers from exponential computational and memory costs in the number of marginals, as transport plans are represented by high-dimensional tensors. We introduce Low-Rank Multimarginal Optimal Transport (LRMOT), which restricts transport plans to tensors with bounded multilinear rank, providing a compact and structured representation of multimarginal couplings. This structure enables efficient algorithms with a low memory footprint. We establish approximation bounds for the resulting low-rank formulations and demonstrate experimentally that the proposed algorithms substantially reduce computational time while achieving solutions of good quality.

Primary area:
optimization
Keywords:
Optimal transport, Tensor decompositions, Optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_dLpnOpenReview ↗
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
  1. 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.

  2. 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
  1. Could the authors provide further clarification on the motivation behind the proposed model?

  2. Could the authors provide an analysis of failure cases?

  3. Could the authors further validate the proposed methods on real-world datasets?

1 comment
AuthorsOpenReview ↗

Response to Reviewer dLpn

We thank Reviewer dLpn for 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)a^{(1)} = \cdots = a^{(d)}. In this case, the optimal transport tensor is given by T⋆=diag(1n,…,1n)\boldsymbol{\mathcal T}^\star = \mathrm{diag}(\tfrac 1n,\ldots,\tfrac 1n) and satisfies rankCP+(T⋆)=n\mathrm{rank}_{\mathrm{CP}+}(\boldsymbol{\mathcal T}^\star) = n. The optimal transport cost is therefore 00. In this setting, with n=20n=20 support points, d=4d=4 marginals, and ε=0.005\varepsilon = 0.005, the Sinkhorn algorithm achieves a transport cost of 6.4×10−36.4\times 10^{-3}, while eCPMOT obtains the following transport costs:

rr468101214161820
cost (×10−3\times 10^{-3})53.626.921.112.211.06.05.45.24.9
Reviewer_i7qVOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes restricting multimarginal transport plans to tensors of bounded multilinear rank (via CP or Tucker factorizations) and derives corresponding solvers, with a specialized alternating scheme for pairwise conditionally-negative-type costs. While the idea is a natural extension of existing low-rank bipartite OT, the theoretical guarantees are extremely loose, the algorithms remain efficient only under strong cost assumptions, the experiments are narrow and fail to demonstrate clear superiority on realistic high-order MOT instances, and the overall contribution is incremental. These shortcomings collectively make the work insufficient for a top venue.

Critical strengths
  1. The hierarchical view that decomposes multimarginal OT into a collection of bipartite transports onto latent measures (and a smaller core MOT) is conceptually clean and unifies several existing low-rank constructions.

  2. On the narrow class of pairwise CNT costs the explicit alternating algorithm is simple, memory-efficient and empirically two orders of magnitude faster than dense Sinkhorn while producing competitive transport costs.

Critical weaknesses
  1. Extremely loose and practically useless approximation bounds.Property 3.4 / Corollary 3.5 give an additive gap of order ∥C∥∞ln⁡((∑nk−d+1)/(r−1))\|C\|_\infty\ln\bigl((\sum n_k-d+1)/(r-1)\bigr). Even after cost normalization the bound is ≈2.4\approx2.4 while observed gaps are 10−210^{-2}; the authors themselves note the bound is far from sharp. A guarantee that does not control the actual error in any useful regime undermines the theoretical justification of the low-rank restriction.

  2. Heavy reliance on restrictive cost structure for computational gains.The only practical algorithm (ECPMOT) and the interesting complexity claims (O(r∑nk)O(r\sum n_k)) require pairwise CNT costs. For general cost tensors the mirror-descent schemes still need access to (or expensive approximations of) the full ndn^d tensor or its mode products, so the claimed “low memory footprint” largely evaporates outside the special case already studied in the literature.

  3. Insufficient and unconvincing experimental evaluation for the multimarginal regime.Almost all quantitative results use d≤4d\le4 synthetic Gaussians or a specially constructed MNIST digit-matching task with d=20d=20 but tiny per-measure support. Comparisons are limited to Sinkhorn variants; there are no large-dd, large-nn, or real multi-omic / particle-system instances that would justify the paper’s motivating claims. Runtime advantages shrink or reverse once Tucker is used, and cost gaps remain visible even at moderate rank.

  4. Incremental novelty relative to existing low-rank OT and tensor literature. The CP and Tucker formulations recover (or are minor variants of) already-published bipartite methods (Scetbon et al., Forrow et al., Halmos et al., Lin et al.). The closest multimarginal precursor (Tran et al., 2021) is only cursorily distinguished. The “explicit” barycentric reformulation is a straightforward consequence of CNT costs and does not constitute a substantial conceptual advance.

  5. Incomplete algorithmic analysis and missing practical safeguards. Convergence of the mirror-descent and alternating schemes is not established beyond empirical observation; the latent-hub initialization (k-means) and the Moore-Penrose approximations needed for general costs are left unanalyzed. There is also no discussion of numerical stability, rank collapse, or how to choose the multilinear ranks in practice—issues that routinely appear in low-rank OT.

Questions for authors

Please refer to the weaknesses above.

Reviewer_JkwPOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Low-Rank Multimarginal Optimal Transport, called LRMOT, which restricts discrete MOT to transport tensors whose unfoldings have bounded nonnegative rank. Such tensors can be stored compactly, so the method avoids the ndn^d memory cost of the full coupling. The authors study two instances of this framework. In TuckerMOT, each marginal is transported to its own latent measure g(k)g^{(k)}, and a small core tensor couples these latent measures. In CPMOT, all marginals are transported to one shared latent measure gg, which connects the problem to barycenter computation. The paper shows that both feasible sets are non-empty and compact, so the minima are attained. It also gives a bound of order ∥C∥∞ln⁡(R/(r−1))\|C\|_\infty \ln(R/(r-1)) on the gap between TuckerMOT and MOT.

For pairwise costs that are conditionally of negative type, the authors introduce explicit CPMOT, in which the support points of the latent measure are optimized directly. Explicit CPMOT is an upper bound of CPMOT. Theorem 4.2 writes both objectives in terms of a variance term VV and a term BB that measures how far apart the means of different marginals are within each component. Corollary 4.3 uses this to bound the extra cost of the explicit solution. The paper provides three solvers. Tucker is solved by mirror descent and CP by mirror descent with Dykstra projections. Explicit CPMOT is solved by an alternating scheme that combines Sinkhorn barycenter steps with closed-form updates of the latent support points. With pairwise costs, the CP solvers cost O(r∑knk)O(r\sum_k n_k) per iteration, while multimarginal Sinkhorn costs O(d∏knk)O(d\prod_k n_k). With two marginals, the Tucker, CP and explicit CP solvers correspond to FRLC, LOT and FC. In the four-marginal Gaussian mixture experiment, ECPMOT runs one to two orders of magnitude faster than multimarginal Sinkhorn, and its transport cost approaches the Sinkhorn cost as rr grows. The paper also reports a matching experiment on 20 MNIST measures and several two-marginal benchmarks.

Critical strengths
  1. The paper gives a clean and well-founded extension of low-rank optimal transport to the multimarginal case. Most earlier work on MOT reduces complexity through structure in the cost, and this paper places the low-rank structure on the transport tensor itself. The formulation through nonnegative multilinear rank covers CP and Tucker decompositions in one framework, with block-term decompositions as an intermediate case. The authors prove that the problems are well posed and reduce general partitions of the modes to the singleton case. They also recover LOT, FC, FRLC and the factored couplings of Tran et al. as special cases. The latent measure view in Figure 2 makes the structure of the coupling easy to understand. This framework is a solid basis for further work on structured MOT, and the writing is rigorous throughout.

  2. Explicit CPMOT is simple, interpretable and effective. Theorem 4.2 shows that ⟨C,T⟩=(d−1)V(T)+B(T)\langle C,T\rangle = (d-1)V(T)+B(T) and F(T)=dV(T)+B(T)F(T) = dV(T)+B(T), which states exactly how the surrogate objective differs from the true transport cost. Corollary 4.3 turns this identity into a usable bound on the optimality gap. The resulting algorithm scales linearly with ∑knk\sum_k n_k and runs on problems where dense MOT cannot be stored, such as the MNIST experiment with 20 marginals. The barycenters it finds are easy to read. The marginal of its plan on the first two measures also has a transport cost close to the two-marginal ECPMOT solution and lower than RCG. In the two-marginal benchmarks of Tables 3, 4 and 5, ECPMOT is the fastest method and its accuracy is close to the best solvers. It also has the highest optimality rate in Table 5.

Critical weaknesses
  1. The general approximation bound is loose. In Appendix B.1, the computable bound equals about 2.37 for a normalized cost, while the observed gap is around 10−210^{-2}. Since Λr≤1\Lambda_r\le 1, the bound improves on ∥C∥∞\|C\|_\infty only when rr exceeds about R/eR/e. The more useful guarantee is Corollary 4.3 in the CP case.

  2. The Tucker solver is less convincing in the multimarginal experiments. In Tables 1 and 2, the Tucker runs reach the 60 second limit in almost all settings, and their cost increases with rr when r≥15r\ge 15. The core problem grows as ∏krk\prod_k r_k, which makes Tucker impractical for the MNIST experiment. The scalability claim of the paper therefore rests mainly on ECPMOT.

Questions for authors
  1. The bound in Property 3.4 depends on RR, the nonnegative CP rank of an optimal MOT plan. Under which conditions on the marginals or the cost is RR small?

  2. Since CP is a special case of Tucker, TuckerMOTr≤CPMOTr\mathrm{TuckerMOT}_r \le \mathrm{CPMOT}_r for the same rank. In Table 1, TUCKER reaches a higher cost than CPMOT for r=10r=10. Does this gap come from the time limit or from the pseudoinverse approximation in Section 5.1?

  3. What are the runtime and the marginal error of ECPMOT in the MNIST experiment with 20 marginals?

Minor points: In Theorem 4.2, B(T)B(T) seems to miss the outer sum ∑sgs\sum_s g_s. Equation 8 uses C(k)C^{(k)} where Equation 7 uses B(k)B^{(k)}. In Lemma C.1, the right side of the second equality should contain φ(xik(k))\varphi(x^{(k)}_{i_k}). The loop at line 18 of Algorithm 8 should run over kk. CPLRMOT in Appendix B.1 seems to refer to explicit CPMOT. Typos include "Additionnal", "comapct", "witch" and "LINEARSUMASSIGNEMENT".

2 comments
AuthorsOpenReview ↗

Reponse to Reviewer JkwP

We are very pleased to hear that you find our paper interesting. In addition to the general response, please find some detailed answers to your questions in this comment.

Computing the nonnegative rank of a tensor is NP-hard (see, for example, "The nonnegative rank of a matrix: hard problems, easy solutions", Shitov (2017)), and we are not aware of any general estimates for this quantity in the literature. However, when the optimal transport tensor is induced by a Monge map of the form \gamma = (\mathrm{Id},a^{(2)},\ldots, a^{(d)})_{\\#} a^{(1)}, we can establish that rankCP+(T⋆)≤n1\mathrm{rank}_{\mathrm{CP}+}(\boldsymbol{\mathcal T}^\star)\le n_1. We refer to "A general condition for Monge solutions in the multi-marginal optimal transport problem", Kim and Pass (2014) for conditions ensuring the existence of such Monge solutions.

The Tucker solver indeed exhibits poor performance in our experiments, both in the multimarginal and bipartite settings. This suggests that future work should focus on approaches based on sparse Tucker cores (e.g., CPMOT, BlockTerm) or exploit additional structural assumptions on the cost tensor C\boldsymbol{\mathcal C}. For instance, Lin et al. (2021) consider a Mahalanobis distance and derive an explicit Tucker formulation in the bipartite case. In the case of Table 1 with r=10r=10, Tucker achieves a mean transport cost of 0.228 (compared to 0.234) when allowed 600 s (instead of 60 s) of computation time. We believe this gap arises because Tucker has either not yet converged or is converging toward a different (and worse) local minimum.

We added the runtime (103 s) and marginal error (10−910^{-9}) of eCPMOT in the MNSIT experiment.

Reviewer_JkwPOpenReview ↗

Response to Authors

Thank you for your response.

My concerns have been addressed.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to all Reviewers

We thank the reviewers for their careful evaluation of our manuscript and for their detailed and constructive feedback. We particularly appreciate the consensual positive assessment of the conceptual framework and mathematical formulation. We summarize our main additions to the updated manuscript below. In the manuscript, modifications are colored in blue.

  1. As noted by Reviewer dLpn (Question 1), the paper would benefit from further motivation for considering low-rank MOT. Such motivation builds on the classical arguments for low-rank formulations in optimal transport, which extend beyond computational considerations (Scetbon et al., Forrow et al., Lin et al.).

a. Overcoming the curse of dimensionality. We added Theorem 4.4 [line 378], which establishes an O(n−12)\mathcal O (n^{-\frac12}) statistical convergence rate for low-rank MOT, mitigating the curse of dimensionality associated with the O(n−1m)\mathcal O(n^{-\frac 1m}) rate in classical MOT. Theorem 4.4:

For every 1≤k≤d1\le k \le d, let a(k)a^{(k)} be a measure supported on the unit ball where the space containing the supports has dimension m<∞m<\infty. Let a^nk(k)\hat a_{n_k}^{(k)} be an empirical distribution comprising nkn_k i.i.d. samples from a(k)a^{(k)}. Then there exists C>0C > 0 such that with probability at least 1−δ1-\delta, ∣eCPMOTr(a^,C)−eCPMOTr(a,C)∣≤Cd∑k=1dr3mlog⁡(r)+log⁡(d/δ)nk.|\mathrm{eCPMOT}_r(\hat{\mathbf{a}},\boldsymbol{\mathcal{C}})-\mathrm{eCPMOT}_r(\mathbf a,\boldsymbol{\mathcal{C}})| \le Cd\sum_{k=1}^d\sqrt{\frac{r^3m\log (r)+\log (d/\delta)}{n_k}}.

b. Clustering, interpretable transport structures, and stability. We added a discussion [line 264] explaining how low-rank MOT can be interpreted as a soft clustering assignment. In particular, the use of latent hubs provides a more interpretable representation of the transport plan, as also observed by Lin et al. Furthermore, low-rank representations can improve stability in the presence of noise, as discussed by Forrow et al.

  1. Every reviewer agreed that the approximation bound is loose (Reviewer JkwP, Weakness 1; Reviewer i7qV, Weakness 1; Reviewer dLpn, Weakness 1).

We acknowledge that the general approximation bound can be very loose, as illustrated in Appendix B.1. To align our results with the state-of-the-art bounds available in the bipartite case (Scetbon et al., 2022), we added Property 3.5 [line 223]. Although this bound is not necessarily sharp, it provides an additional convergence guarantee and can be tight when the Lipschitz constant is small. Moreover, when the multilinear ranks reach the support sizes of the corresponding marginals, the original MOT problem is recovered exactly, and the approximation gap vanishes. Property 3.5:

Assume that C:Xd→R+\boldsymbol{\mathcal C} : \mathcal X^d \to \mathbb R_+ is LL-Lipschitz with respect to each variable. Then, for any r≥1r\ge 1, taking q=⌊r1/d⌋q=\lfloor r^{1/d}\rfloor, we have 0≤TuckerMOTr(a,C)−MOT(a,C)≤2dLmax⁡kN⌊log⁡2q⌋(supp(a(k))).0 \le \mathrm{TuckerMOT}_{\mathbf r}(\mathbf{a},\boldsymbol{\mathcal{C}}) - \mathrm{MOT}(\mathbf{a},\boldsymbol{\mathcal{C}}) \le 2dL\max_{k}\mathcal N_{\lfloor \log_2 q \rfloor}(\mathrm{supp}(a^{(k)})).

  1. Reviewer i7qV's Weakness 2 concerns the computational scalability of our methods beyond the pairwise CNT setting.

We agree that the computational advantages of our methods deserve further clarification beyond the pairwise CNT setting. While eCPMOT exploits this particular structure, the computational benefits of CPMOT are not restricted to pairwise costs. We have therefore expanded the discussion [line 1728] to explain how CPMOT can also exploit costs structured according to a graphical model of maximum degree α\alpha. In this setting, the per-iteration computational complexity is reduced to O(drnα)\mathcal O (drn^\alpha).

This encompasses a substantially broader class of structured costs. Such structured cost functions are also relevant in applications, as illustrated by Haasler et al. (2021) and Strössner et al. (2023).

  1. Reviewer i7qV's Weakness 3 and Reviewer dLpn's Question 3 concern the need for additional large-scale multimarginal experiments.

We would be eager to investigate applications to real-world data, should a suitable public dataset be available that we are not yet aware of. In the meantime, to further assess the practical relevance of our methods, we followed the algorithmic MOT literature and reproduced [line 881] the high-dimensional setting (d=480d=480) from Section 6 of "Multi-marginal Optimal Transport with a Tree-structured Cost and the Schrödinger Bridge Problem" (Haasler et al.), where the objective is to estimate an ensemble flow on a hidden Markov chain. Our experiments show that CPMOT correctly tracks the population's center of mass and that the estimation quality improves as the rank rr increases.

AuthorsOpenReview ↗

Response to all Reviewers

  1. Reviewer i7qV's Weakness 4 points to the work of Tran et al. (2021) as a precursor to the low-rank MOT problem.

We agree that the low-rank MOT solvers arising from our framework are extensions of existing solvers in the bipartite case. Tran et al. (2021) define the F-MMOT problem where the transport tensor is subject to rank constraints. However, their focus is on MMOT-DC, which does not impose any constraints on the transport tensor. Instead, it introduces a penalization term of the form εKL(P∣∣PT)\varepsilon \mathrm{KL}(P || P_{\mathcal T}), where PTP_{\mathcal T} is a rank-(1,…,1)(1,\ldots,1) tensor constructed from the full tensor PP and a tuple partition T\mathcal T of the modes. Therefore, they neither solve a low-rank MOT problem nor study the solutions of F-MMOT. This distinction explains why their work does not directly address the problem considered in our paper.

  1. Additional convergence analysis is requested in Reviewer i7qV's Weakness 5.

We added the following statement [line 1770] establishing the O(1/T)\mathcal O(1/T) convergence rate of CPMOT to a stationary point: Define Fε(ξ)=f(ξ)−εh(ξ)F_\varepsilon(\xi) = f(\xi)-\varepsilon h(\xi) the function we aim to minimize. For any η>0\eta > 0 and ξ∈Ξ\xi\in\Xi, define Gε(ξ,η)=arg⁡min⁡ζ∈Ξ ⟨∇Fε(ξ),ζ⟩+1ηKL(ζ,ξ),G_\varepsilon(\xi,\eta) = \arg\min_{\zeta\in\Xi}\, \langle\nabla F_\varepsilon(\xi), \zeta\rangle + \frac 1\eta \mathrm{KL} (\zeta,\xi), and Δε(ξ,η)=1η2[KL(ξ,Gε(ξ,η))+KL(Gε(ξ,η),ξ)].\Delta_\varepsilon(\xi,\eta) = \frac{1}{\eta^2} \big[\mathrm{KL}(\xi, G_\varepsilon(\xi,\eta)) + \mathrm{KL}(G_\varepsilon(\xi,\eta),\xi)\big]. Assume C\boldsymbol{\mathcal{C}} has finite entries, and that the initial point ξ0∈ri(Ξ)\xi_0\in \mathrm{ri}(\Xi). Then, for any number of iteration T≥1T\ge 1, taking the constant step size η=1/2Lε\eta = 1/2 L_\varepsilon, we have min⁡0≤t≤T−1Δε(ξt,η)≤4LεD0T,\min_{0\le t\le T-1} \Delta_\varepsilon(\xi_t,\eta)\le \frac{4L_\varepsilon D_0}{T}, where D0=Fε(ξ0)−min⁡ξ∈ΞFε(ξ)D_0 = F_\varepsilon(\xi_0)-\min_{\xi\in\Xi} F_\varepsilon(\xi) and LεL_\varepsilon is defined in Eq. (16).

We also wish to emphasize that eCPMOT converges regardless of whether k-means initialization is used (Appendix G.1). Furthermore, the Moore–Penrose pseudoinverse mentioned in Section 5.1 is neither required by TuckerMOT nor used in Algorithm 5.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.