Collision-based Dynamics for Multi-Marginal Optimal Transport
Mohsen Sadr and Hossein Gorji · 2024
Read Collision-based Dynamics for Multi-Marginal Optimal Transport by Mohsen Sadr and Hossein Gorji (2024) 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-2412-16385.txt.
Introduction
Mohsen Sadr and Hossein Gorji propose in 2024 a collision-based method for multi-marginal optimal transport, the problem of matching several distributions at once at least total cost. Classical solvers swell badly as samples and margins multiply. Their idea borrows from gas kinetics, where collisions shuffle particles toward equilibrium.
Random pairwise swaps of sample indices, Monte Carlo style, nudge the matching toward optimal. Cost and memory grow only in step with the sample count, a linear scaling that suits high dimensions. Benchmark examples beat state-of-the-art solvers on efficiency. Physics-inspired dynamics keep proving fertile ground for hard optimization problems far from physics itself.
Catalog record
| CREATOR | Mohsen Sadr and Hossein Gorji |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-16385
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Collision-based Dynamics for Multi-Marginal Optimal Transport Thanks: Emails: [email protected] , [email protected] Mohsen Sadr: Paul Scherrer Institute, Forschungsstrasse 111, CH-5232 Villigen, Switzerland. Hossein Gorji: Laboratory for Computational Engineering, Empa, Dübendorf, Switzerland. Mohsen Sadr and Hossein Gorji Abstract . Inspired by the Boltzmann kinetics, we propose a collision-based dynamics with a Monte Carlo solution algorithm that approximates the solution of the multi-marginal optimal transport problem via randomized pairwise swapping of sample indices. The computational complexity and memory usage of the proposed method scale linearly with the number of samples, making it highly attractive for high-dimensional settings. In several examples, we demonstrate the efficiency of the proposed method compared to the state-of-the-art methods. 1. Introduction Since its introduction by Gaspard Monge [ 1 ] and seminal contributions by Leonid Kantorovich [ 2 ] , the Optimal Transport (OT) has evolved into a rich mathematical framework with fruitful theoretical properties. At its core, it gives a geometrically intuitive basis to compare and interpolate probability distributions, leading to wide-range of applications across many fields. This includes interpolation between images [ 3 ] , clustering dataset [ 4 ] , surrogate models [ 5 ] , calibration of stochastic processes [ 6 ] , and finding the N-body particle distribution function in density functional theory [ 7 ] . However, the computational complexity associated with the underlying optimization problem limits the use of OT in large datasets. This is due to the fact that the OT problem is inherently linear programming over an infinite-dimensional space, resulting in computationally intensive optimization. The problem can even become intractable if multi-marginals are considered. Though non-exclusively, we can categorize the main computational algorithms for numerical solution to the OT problem as the following. Linear programming. This is the direct approach in solving the OT problem, also known as Earth Mover’s Distance in the literature [ 8 ] . Linear programming has been applied mainly to the two-marginal OT problem, where the computational complexity becomes \mathcal{O}(N_{p}^{3}\log(N_{p})) for N_{p} number of samples per marginal. Fast EMD algorithms use the network simplex with empirical computational complexity of \mathcal{O}(N_{p}^{2}) [ 9 ] . Regularization via entropy. By incorporating entropy in the cost functional of the two-marginal OT, one derives a relaxed version of the OT problem [ 10 , 11 ] . The resulting optimization problem is convex and can be solved efficiently using the so-called Sinkhorn method, with the computational complexity of \mathcal{O}(N_{p}^{2}) . Dynamic processes. Optimal maps can be described by dynamic processes. For example, the fluid dynamic formulation, given by Benamou-Brenier dynamics, describes the OT problem in the form of the Hamilton-Jacobi dynamics [ 12 ] . Another class of dynamic formulation is given by marginal preserving processes, where OT (and its entropy regularized version) is recovered at the stationary state [ 13 ] . In particular, Orthogonal Coupling Dynamics [ 14 ] introduces an efficient algorithm with the computational complexity of \mathcal{O}(N_{p}\log(N_{p})) . Reduction to assignment problem. As shown by [ 15 ] , OT in discrete setting is closely related to the assignment problem. A notably efficient approximate solution is introduced by Iterative Swapping Algorithm (ISA) [ 16 , 17 ] , where a near-optimal permutation of discrete points is found via consecutive swaps of samples in each marginal. The ISA has the computational complexity of \mathcal{O}(N_{p}^{2}) , and is the closest method to what we develop here. Other notable approximate methods include moment-based methods [ 18 , 19 ] , simulated annealing [ 20 ] , and sliced-Wasserstein [ 21 , 22 ] . Contributions. We focus on the multi-marginal OT problem in the discrete setting, where only samples of the marginals are provided. Unlike the optimal assignment approach, which looks for the optimal permutation of samples, we iteratively improve the permutation of samples by pair-wise swapping. Instead of checking all possible swaps, which is pursued in ISA, we devise a random algorithm inspired by Boltzmann kinetics, where binary collisions are performed by randomly selecting collision pairs. We formalize both ISA and our collision-based algorithm, and motivate their consistency. We show that in the case of the OT problem with L^{p} -transport cost, the complexity of checking the condition for a swap to be accepted/rejected is independent of number of samples. Furthermore, we show that the complexity of the collision-based method scales linearly with number of samples. We empirically investigate its convergence behaviour and observe exponential convergence to the stationary solution, regardless of number of samples/marginals/dimension. In several toy examples, we show the error and performance of the proposed method compared to Sinkhorn and EMD. Then, as a show case, we assess the flexibility of the method in finding the optimal map in a five-marginal problem, which allows us to learn a map between normal and other target densities. As an application in Machine Learning, we demonstrate the performance of collision-based method in finding the distribution of the Wasserstein distance in the Japanese female facial expression and butterfly datasets. Definitions, Notations, and Problem Setup. Let \mathcal{P}(\mathcal{X}_{i}) be the space of non-negative Borel measures over \mathcal{X}_{i}\subset\mathbb{R}^{n} , and \displaystyle\mathcal{P}_{2}(\mathcal{X}_{i})\mathrel{\mathop{:}}=\left\{\mu\in\mathcal{P}(\mathcal{X}_{i})\bigg|\int_{\mathcal{X}_{i}}\lVert x\rVert_{2}^{2}\mu(dx)<\infty\right\} (1) with \lVert.\rVert_{2} the usual L^{2} -Euclidean norm. Consider K probability measures \mu_{i}\in\mathcal{P}_{2}(\mathcal{X}_{i}) with i\in\{1,...,K\} , and vanishing on (n-1) -rectifiable sets [ 23 ] . We are interested in the Multi-Marginal Optimal Transport problem (MMOT), which seeks the minimization \displaystyle\pi_{\textrm{opt}}\mathrel{\mathop{:}}=\argmin_{\pi\in\Pi(\mu_{1},...,\mu_{K})}\int_{\mathcal{X}}c(x_{1},...,x_{K})\pi(dx)\ , (2) where \mathcal{X} is the product set \mathcal{X}\mathrel{\mathop{:}}=\mathcal{X}_{1}\times...\times\mathcal{X}_{K} . The optimization is constrained on \Pi , which is the set of coupling measures \displaystyle\Pi(\mu_{1},...,\mu_{K})\mathrel{\mathop{:}}=\left\{\pi\in\mathcal{P}_{2}(\mathcal{X})\bigg|\textrm{proj}_{i}(\pi)=\mu_{i}\ \forall i\in\{1,...,K\}\right\} (3) and \textrm{proj}_{i}:\mathcal{X}\to\mathcal{X}_{i} is the canonical projection. In order for MMOT to have a solution, it is sufficient to assume that the cost c:\mathcal{X}\to\mathbb{R} is lower-semicontinuous [ 23 ] . In general there is no guarantee that the optimal transport plan, i.e. \pi_{\textrm{opt}} , is induced by an optimal map. The existence of the optimal map entails further constraints on the cost. One interesting setting, which has been analyzed thoroughly, is when K=2 and c(x_{1},x_{2})=\lVert x_{1}-x_{2}\rVert_{2}^{2} . For this L^{2} -OT setting, the optimal map exists and is unique [ 24 , 25 ] . The generalization of L^{2} -OT to MMOT has been carried out by the seminal work of Gangbo and Swiech [ 23 ] . Consider \displaystyle c(x_{1},...,x_{K})=\sum_{i=1}^{K}\sum_{j=i+1}^{K}\frac{1}{2}\lVert x_{i}-x_{j}\rVert_{2}^{2}\ , (4) the optimal plan \pi_{\textrm{opt}} then takes a deterministic form and is concentrated on optimal maps. In fact, the equivalent form of ( 2 ) is given by optimization over the maps \{T_{i}\}\in\mathcal{T}_{K} , where \displaystyle\mathcal{T}_{K} \displaystyle\mathrel{\mathop{:}}= \displaystyle\left\{T=\{T_{i}\}_{i=1,..,K}\ |\ \ T_{i}:\mathcal{X}_{1}\to\mathcal{X}_{i},\ T_{i}\#\mu_{1}=\mu_{i},\ T_{1}=\textrm{id}\right\} (5) such that \displaystyle\inf\left\{\int_{\mathcal{X}_{1}}\sum_{i=1}^{K}\sum_{j=i+1}^{K}\frac{1}{2}\lVert T_{i}(x_{1})-T_{j}(x_{1})\rVert_{2}^{2}\ \mu_{1}(dx_{1})\ \ \bigg|\ \{T_{i}\}_{i=1,...,K}\in\mathcal{T}_{K}\right\} (6) is attained [ 26 , 23 ] . Though our devised algorithm is not restricted to a specific choice of c(.) , in order to keep the study focused, we target the Gangbo-Swiech setting and refer to it as L^{2} -MMOT problem. It is clear that the setting reduces to L^{2} -OT for K=2 . We refer the reader to [ 27 ] and references therein for detailed analysis of existence and uniqueness in MMOT problem. Instead of direct access to \{\mu_{i}\} , we consider the scenario where only N_{p} independent samples of each marginal, i.e. \hat{X}^{(i)}=\{\hat{X}_{1}^{(i)},...,\hat{X}_{N_{p}}^{(i)}\}\sim\mu_{i} , is known. Given \{\hat{X}^{(i)}\} for i\in\{1,...,K\} , the pursued algorithm seeks to find estimates of \pi_{\textrm{opt}} along