Polynomial-time algorithms for multimarginal optimal transport problems with structure
From MaRDI portal
Abstract: Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly(n,k) time. We develop a unified algorithmic framework for solving MOT in poly(n,k) time by characterizing the "structure" that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly(n,k) time. Second, our framework makes it much simpler to develop poly(n,k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle -- which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing poly(n,k) time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly(n,k) runtime; moreover, we provide the first poly(n,k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n,k) time algorithms, even for approximate computation. Together, these three structures encompass many -- if not most -- current applications of MOT.
Recommendations
- Hardness results for multimarginal optimal transport problems
- Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- Multi-marginal optimal transport: theory and applications
- Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A numerical method to solve multi-marginal optimal transport problems with Coulomb cost
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
- A simple min-cut algorithm
- An entropy minimization approach to second-order variational mean-field games
- Barycenters in the Wasserstein space
- Combinatorial approaches to Monte Carlo estimation of network lifetime distribution
- Computational Complexity of Network Reliability Analysis: An Overview
- Computing correlated equilibria in multi-player games
- Convex majorization with an application to the length of critical paths
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Density functional theory and optimal transportation with Coulomb cost
- Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
- Discrete Wasserstein barycenters: optimal transport for discrete data
- Distributionally Robust Linear and Discrete Optimization with Marginals
- Estimates for the Distribution Function of a Sum of Two Random Variables When the Marginal Distributions are Fixed
- Extremal probability bounds in combinatorial optimization
- Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
- Generalized solutions and hydrostatic approximation of the Euler equations
- Geometric algorithms and combinatorial optimization.
- Graphical models, exponential families, and variational inference
- Hardness results for multimarginal optimal transport problems
- Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness
- scientific article; zbMATH DE number 1670534 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 1775454 (Why is no real title available?)
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 795224 (Why is no real title available?)
- scientific article; zbMATH DE number 7370561 (Why is no real title available?)
- Iterative Bregman projections for regularized transportation problems
- Learning Mixtures of Product Distributions over Discrete Domains
- Learning with submodular functions: a convex optimization perspective
- Matching for teams
- Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations
- Multi-Marginal Optimal Transport and Probabilistic Graphical Models
- Numerical methods for matching for teams and Wasserstein barycenters
- On the \(n\)-coupling problem
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Persistency model and its applications in choice modeling
- Polynomial algorithms for estimating network reliability
- Polynomial algorithms in linear programming
- Price of correlations in stochastic optimization
- Probabilistic graphical models.
- Probabilistic PERT
- Random variables with maximum sums
- Reliable circuits using less reliable relays
- Robustness against dependence in PERT: An application of duality and distributions with known marginals
- Scalable Bayes via barycenter in Wasserstein space
- Stochastic Bounds on Distributions of Optimal Value Functions with Applications to PERT, Network Flows and Reliability
- Tensor Decompositions and Applications
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The Complexity of Ferromagnetic Ising with Local Fields
- The dual least action problem for an ideal, incompressible fluid
- The ellipsoid method and its consequences in combinatorial optimization
- The Least Action Principle and the Related Concept of Generalized Flows for Incompressible Perfect Fluids
- Treewidth: Structure and Algorithms
- Wasserstein Barycenters Are NP-Hard to Compute
Cited in
(10)- Hardness results for multimarginal optimal transport problems
- Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with Monge costs
- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
- Scalable computation of dynamic flow problems via multimarginal graph-structured optimal transport
- Efficient and exact multimarginal optimal transport with pairwise costs
- Graph-structured tensor optimization for nonlinear density control and mean field games
- Constrained Hellinger-Kantorovich barycenters: least-cost soft and conic multimarginal formulations
- Computation of robust option prices via structured multimarginal martingale optimal transport
- Distributionally robust optimization
This page was built for publication: Polynomial-time algorithms for multimarginal optimal transport problems with structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038667)
