Stability of the Monge Map in Semi-Dual Optimal Transport

• URL: http://arxiv.org/abs/2605.05569v2
• Date: Fri, 08 May 2026 22:28:15 GMT
• Title: Stability of the Monge Map in Semi-Dual Optimal Transport
• Abstract summary: We show that the semi-dual formulation of the optimal transport problem has a degenerate saddle-point structure.<n>We derive necessary and sufficient conditions for the convergence of Monge maps without requiring optimality of the dual potential.
• Score: 2.952087147464148
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper shows that the semi-dual formulation of the optimal transport problem has a degenerate saddle-point structure, and that its numerical solution is equivalent to solving a constrained optimization problem. We derive necessary and sufficient conditions for the convergence of Monge maps without requiring optimality of the dual potential. This analysis helps explain why, in practice, numerical algorithms often require more iterations to update the transport map than the potential.

Related papers

• Variational Entropic Optimal Transport [67.76725267984578]
  We propose Variational Entropic Optimal Transport (VarEOT) for domain translation problems.<n>VarEOT is based on an exact variational reformulation of the log-partition $log mathbbE[exp(cdot)$ as a tractable generalization over an auxiliary positive normalizer.<n> Experiments on synthetic data and unpaired image-to-image translation demonstrate competitive or improved translation quality.
  arXiv  Detail & Related papers  (2026-02-02T15:48:44Z)
• Convex Physics Informed Neural Networks for the Monge-Ampère Optimal Transport Problem [49.1574468325115]
  Optimal transportation of raw material from suppliers to customers is an issue arising in logistics.<n>A physics informed neuralnetwork method is advocated here for the solution of the corresponding generalized Monge-Ampere equation.<n>A particular focus is set on the enforcement of transport boundary conditions in the loss function.
  arXiv  Detail & Related papers  (2025-01-17T12:51:25Z)
• A Computational Framework for Solving Wasserstein Lagrangian Flows [48.87656245464521]
  In general, the optimal density path is unknown, and solving these variational problems can be computationally challenging. We propose a novel deep learning based framework approaching all of these problems from a unified perspective. We showcase the versatility of the proposed framework by outperforming previous approaches for the single-cell trajectory inference.
  arXiv  Detail & Related papers  (2023-10-16T17:59:54Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport [0.483420384410068]
  We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.
  arXiv  Detail & Related papers  (2021-10-25T06:52:45Z)
• Scalable Computation of Monge Maps with General Costs [12.273462158073302]
  Monge map refers to the optimal transport map between two probability distributions. We present a scalable algorithm for computing the Monge map between two probability distributions.
  arXiv  Detail & Related papers  (2021-06-07T17:23:24Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• Fast Unbalanced Optimal Transport on a Tree [40.60905158071766]
  This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time. Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric.
  arXiv  Detail & Related papers  (2020-06-04T08:43:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.