Neural Estimation for Scaling Entropic Multimarginal Optimal Transport

Dor Tsur, Ziv Goldfeld, Kristjan Greenewald, Haim Permuter · 2025

Read Neural Estimation for Scaling Entropic Multimarginal Optimal Transport by Dor Tsur, Ziv Goldfeld, Kristjan Greenewald, Haim Permuter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00573.txt.

Introduction

Dor Tsur and co-authors make, in 2025, a heavy transport computation dramatically cheaper. Multimarginal optimal transport matches several distributions at once, but the standard smoothed algorithm's cost explodes as data and distribution counts grow. Their framework swaps the giant computation for neural networks trained on small batches.

Cost then depends on batch size, not dataset size, unlocking far larger problems. The authors prove error bounds for the estimator and test it against the standard algorithm, finding speedups of orders of magnitude and feasible runs at scales previously out of reach. An extension handles shape alignment problems. The module is designed to slot into large learning pipelines.

Catalog record

CREATORDor Tsur, Ziv Goldfeld, Kristjan Greenewald, Haim Permuter
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-00573

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Neural Estimation for Scaling Entropic Multimarginal Optimal Transport Dor Tsur, Ziv Goldfeld, Kristjan Greenewald, Haim Permuter Abstract Multimarginal optimal transport (MOT) is a powerful framework for modeling interactions between multiple distributions, yet its applicability is bottlenecked by a high computational overhead. Entropic regularization provides computational speedups via the multimarginal Sinkhorn algorithm, whose time complexity, for a dataset size n n and k k marginals, generally scales as O ⁡ ( n k ) O(n^{k}) . However, this dependence on the dataset size n n is computationally prohibitive for many machine learning problems. In this work, we propose a new computational framework for entropic MOT, dubbed Neural Entropic MOT (NEMOT), that enjoys significantly improved scalability. NEMOT employs neural networks trained using mini-batches, which transfers the computational complexity from the dataset size to the size of the mini-batch, leading to substantial gains. We provide formal guarantees on the accuracy of NEMOT via non-asymptotic error bounds. We supplement these with numerical results that demonstrate the performance gains of NEMOT over Sinkhorn’s algorithm, as well as extensions to neural computation of multimarginal entropic Gromov-Wasserstein alignment. In particular, orders-of-magnitude speedups are observed relative to the state-of-the-art, with a notable increase in the feasible number of samples and marginals. NEMOT seamlessly integrates as a module in large-scale machine learning pipelines, and can serve to expand the practical applicability of entropic MOT for tasks involving multimarginal data. 1 Introduction Optimal transport (OT) villani2009optimal ; santambrogio2015optimal is a versatile framework for modeling complex relationships between distributions, which has had a tangible impact in machine learning solomon2015convolutional ; tolstikhin2017wasserstein ; arjovsky2017wasserstein , statistics carlier2016vector ; chernozhukov2017monge , economics galichon2018optimal , and applied mathematics santambrogio2015optimal . In many applications, one seeks to account for interaction between more than two marginals, which naturally leads to the multimarginal OT (MOT) setting pass2015multi . Given k\geq 2 marginal distributions \bm{\mu}^{k}\coloneqq(\mu_{1},\dots,\mu_{k}) each supported on \mathcal{X}_{1},\ldots,\mathcal{X}_{k} , respectively, and cost function c:\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{k}\to[0,\infty) , the MOT problem reads \mathsf{M}\mathsf{O}\mathsf{T}_{c}(\bm{\mu}^{k})\coloneqq\inf_{\pi\in\Pi(\bm{\mu}^{k})}\int c(\mathbf{x}^{k})d\pi(\mathbf{x}^{k}), (1) where \Pi(\bm{\mu}^{k}) is the set of all joint distributions on \bigotimes_{i=1}^{k}\mathcal{X}_{i} whose i th marginal is \mu_{i} , for i=1,\ldots,k . MOT was initially employed for certain operational problems in physics cotar2013density ; benamou2019generalized , but more recently it has found applications in machine learning, spanning multi-domain image translation cao2019multi , Bayesian learning srivastava2018scalable , distributionally robust optimization chen2022distributionally , adversarial learning trillos2023multimarginal , fair representation learning mehta2023efficient and multiview embedding matching piran2024contrasting . However, the scalability of such algorithms has been hindered by the computational overhead of MOT, which requires solving an exponentially large (in k ) linear program. In fact, altschuler2021hardness show that a polynomial-time deterministic algorithm for MOT does not exist for a variety of cost structures, even when the cost tensor is sparse. In the bimarginal case, entropic regularization is key for the empirical successes of OT. By leveraging Sinkhorn’s fixed-point iteration algorithm cuturi2013sinkhorn , entropic OT reduces the computational complexity while enjoying fast statistical estimation rates genevay2019sample ; mena2019statistical . Entropic regularization also leads to computational gains in the multimarginal setting via an extension of Sinkhorn’s algorithm lin2022complexity . However, multimarginal Sinkhorn directly computes a k -wise joint distribution (as an n^{k} -sized tensor), resulting in an exponential in k scaling of the memory and computational costs. One approach to reduce this complexity is to restrict attention to sparse cost structures, where the k -fold cost function in ( 1 ) decomposes into a sum of a small number of pairwise costs (e.g., circle or tree cost structures). Such sparsity reduces the runtime of Sinkhorn to polynomial in (n,k) haasler2021multi ; ba2022accelerating ; altschuler2023polynomial , but the dependence on the entire dataset size n remains. This is computationally prohibitive for large real-world datasets. 1.1 Contributions We develop a methodology for scaling up the entropic MOT (EMOT) computation. Drawing upon recent neural estimation approaches belghazi2018mutual ; sreekumar2022neural ; tsur2023neural ; wang2024neural , we propose the neural EMOT (NEMOT) framework, which optimizes an approximation of the dual EMOT objective over a set of neural network parameters. NEMOT estimates both the EMOT cost and transportation plan by harnessing deep learning tools, such as mini-batch gradient-based optimization. This transfers the computational cost of our algorithm to the mini-batch size b (as opposed to n ), which results in a marked increase in scalability compared to multimarginal Sinkhorn. Furthermore, while existing approaches often rely on restrictive assumptions on the cost function (e.g., sparsity) to alleviate some computational burden, NEMOT can handle massive datasets with arbitrary costs. As such, NEMOT can be seamlessly integrated as a module into larger machine learning pipelines as a loss or regularizer. To facilitate a principled implementation of NEMOT, we provide non-asymptotic bounds on the cost and plan estimation erros. Under mild assumptions, a NEMOT realized by a m -neuron shallow ReLU network and n data samples from each of the k distributions is guaranteed to estimate the cost \mathsf{M}\mathsf{O}\mathsf{T}_{c}(\bm{\mu}^{k}) within an additive error of O(\mathsf{poly}(\epsilon^{-1})k(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})) . We further show, that the same bound, up to an extra multiplicative factor of 1/\epsilon , holds for the Kullback-Leibler (KL) divergence between the optimal EMOT plan and its neural estimate. The theory is supplemented by empirical results that demonstrate the computational advantage of NEMOT over the multimarginal Sinkhorn algorithm. NEMOT exhibits speedups in orders of magnitude, unlocking new regimes of possible (b,n,k) values for EMOT and applications thereof. We present extensions of NEMOT to the multimarginal Gromov-Wasserstein (MGW) problem, which gained recent popularity for tasks involving alignment of heterogeneous datasets alvarez2018gromov ; xu2019gromov . To that end, we reformulate the MGW as an alternating optimization between NEMOT and certain auxiliary matrices. 1.2 Related Work MOT has seen increasing applications as a means to alter the distribution of learned representations in a way that enforces criteria across multiple domains. In generative modeling, cao2019multi introduces a multimarginal extension of the Wasserstein GAN arjovsky2017wasserstein to address the multimarginal matching problem. In multi-view learning, the multimarginal Sinkhorn algorithm is employed for distribution matching of multiple learned embeddings piran2024contrasting . mehta2023efficient leveraged MOT with 1 -Wasserstein cost to regularize data representations, with applications to fairness, harmonization, and generative modeling. In the context of adversarial classification, trillos2023multimarginal shows the equivalence between MOT and certain adversarial multiclass classification problems, allowing the derivation of optimal robust classification rules. More recently, noble2024tree proposed to solve high-dimensional star-structured EMOT problems via diffusion processes. However, this approach does not generalize to other cost functions, leaving barycenter computation as its main application. For unregularized MOT, zhou2024efficient suggests solving a simplified surrogate problem over a directed tree, but their computational complexity also scales with n . When only two marginals are present, EMOT reduces to the ubiquitous entropic optimal transport problem (EOT). Neural estimation of EOT has seen significant success via several different approaches. For instance, seguy2017large introduced a neural estimation framework based on the semi-dual formulation of the entropic OT problem. Their method efficiently computes the optimal transport plan by parametrizing the dual potentials with neural networks. Building on this, daniels2021score proposed a score-based generative approach that not only estimates the Sinkhorn coupling via neural network parametrization but also incorporates stochastic dynamics to sample from the resulting transport plan. More recently, mokrov2023energy combined the semi-dual entropic OT formulation with energy-based models, further increasing modeling capacity

Read the complete text