Stability of the Monge Map in Semi-Dual Optimal Transport
Anton Selitskiy, David Millard · 2026
Read Stability of the Monge Map in Semi-Dual Optimal Transport by Anton Selitskiy, David Millard (2026) 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-2605-05569.txt.
Introduction
Optimal transport asks the cheapest way to reshape one distribution into another. Anton Selitskiy and David Millard study the stability of the Monge map, the optimal reshaping itself, in the semi-dual form of the problem. They show that form has a degenerate saddle-point structure, and solving it amounts to a constrained optimization problem.
They derive exact conditions for when the transport maps converge, without demanding that the dual potential be optimal. The result explains a familiar annoyance: numerical solvers often need more iterations to settle the map than to settle the potential.
Catalog record
| CREATOR | Anton Selitskiy, David Millard |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05569
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stability of the Monge Map in Semi-Dual Optimal Transport Anton Selitskiy, David Millard 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. 1 Introduction Recently, optimal transport (OT) has become a powerful tool in machine learning, statistics, and signal processing. From a theoretical perspective, many modern generative models — including variational autoencoders (VAEs), generative adversarial networks (GANs), diffusion models, and flow-based models — can be interpreted as approximations of transport processes between probability distributions. For instance, GANs can be viewed as learning a map that transports a simple latent distribution (e.g., uniform or Gaussian) to complex data distribution (e.g., a highly nonlinear data generating distribution). Similarly diffusion models describe stochastic flows that gradually transform one distribution into another. These connections suggest that optimal transport provides a unifying mathematical framework for generative modeling , where learning corresponds to approximating transport maps or transport dynamics between distributions. This work is motivated by neural optimal transport (NOT) algorithm introduced in 29 , which is closely related to the (2,2) -WGAN from 23 and other WGAN formulations. Later, NOT algorithm was extended to weak formulations in 20 . These approaches rely on the semi-dual formulation of optimal transport 1 1 1 This formulation presents already in the seminal work 16 , while the term “semi-dual” appears in 5 . together with amortized optimization techniques introduced in 6 , later interpreted as measurable selection mechanisms in the theory of integrands. Altogether, these works exploit the existence (and, for quadratic cost, uniqueness) of optimal transport maps, but do not provide convergence guarantees for the learned maps. Many papers containing convergence estimates implicitly assume that the transport map exists and that the optimization problem is well-posed; however, these assumptions are mathematically nontrivial and may fail in practice, leading to misleading or impractical conclusions (see Sec. 5 ). In this paper, we show that the semi-dual optimal transport problem possesses a degenerate saddle-point structure: at the optimal transport map, the objective functional becomes independent of the potential. We provide an estimate of the transport map which is independent of the potential: \|T-T^{\star}\|_{L_{2}}^{2}\lesssim{\left|\mathbb{E}[c(x,T(x))]-W_{2}(\mu,\nu)^{2}\right|}+d_{KR}(T_{\sharp}\mu,\nu). (1) While many works assess convergence through the approximation gap and the discrepancy between generated and target distributions, to the best of our knowledge such estimates have not been formulated explicitly in the form of ( 1 ). Early works on the numerical solution of the semi-dual OT problem approximated the conjugate potential using an inner optimization loop 30 . Later, with neural network parametrizations it was observed that performing multiple updates of the transport map leads to better performance 22 . We provide a theoretical explanation for this phenomenon by interpreting the problem as a constrained optimization task and relating it to a continuous-time two-timescale dynamical system. 2 Optimal Transport Problem 2.1 Notation We will assume that X is a complete separable metric space. Such spaces are referred to as Polish spaces. In practice, we consider either X=\mathbb{R}^{n} or a compact subset of \mathbb{R}^{n} . By \mathcal{P}(X) we denote the space of probability measures defined on the Borel \sigma -algebra \mathcal{B}(X), i.e., the smallest \sigma -algebra generated by open subsets of X. \mathcal{P}_{p}(X) denotes subspace of \mathcal{P}(X) having p th moments. Assume that Y is a Polish space and a lower semicontinuous (l.s.c.) 2 2 2 Continuous functions are l.s.c. cost function is defined: c\colon X\times Y\to[0,\infty). Later, we assume that X and Y are compact sets in \mathbb{R}^{n} endowed with metric d(x,y) and cost c(x,y)=\frac{1}{p}d(x,y)^{p}. (2) Letting \mu\in\mathcal{P}(X) and \nu\in\mathcal{P}(Y) be probability measures we can consider two probability spaces (X,\mathcal{X},\mu) and (Y,\mathcal{Y},\nu) with \mathcal{X}=\mathcal{B}(X) and \mathcal{Y}=\mathcal{B}(Y). 2.2 Monge Formulation For a \mathcal{X}|\mathcal{Y} -measurable function T\colon X\to Y, the measure \nu such that \nu(B)=\mu(T^{-1}(B)) for all B\in\mathcal{Y} is called a push-forward measure of \mu by T . In this case, the following notation is used: \nu=T_{\sharp}\mu\ (=\mu\circ T^{-1}) . Denote by T(\mu,\nu) the space of measurable (Borel) functions T\colon X\to Y, for which \nu is a push-forward measure of \mu. Elements of T(\mu,\nu) will be referred to as transport maps . The Monge problem is to find a transport map T^{*}\colon X\to Y that minimizes the transport cost MP(\mu,\nu,c)=\underset{T\in T(\mu,\nu)}{\inf}\int\limits_{X}c(x,T(x))d\mu(x). (3) If the infimum is reached on some function T^{*}, then T^{*} is called the optimal transport map. Sometimes, the class T(\mu,\nu) is empty (see Table 1 ). 2.3 Kantorovich Formulation Denote by \Pi(\mu,\nu) the set of probability measures \pi on the product space (X\times Y,\mathcal{X}\otimes\mathcal{Y}) with prescribed marginal distributions: \pi(A\times Y)=\mu(A), and \pi(X\times B)=\nu(B),\quad\forall A\in\mathcal{X},\ B\in\mathcal{Y}. Measures \pi\in\Pi(\mu,\nu) are called transport (or transportation) plans . 3 3 3 The set \Pi(\mu,\nu) is nonempty; for instance it contains the product measure \mu\otimes\nu . The Kantorovich problem consists in finding a transport plan \pi^{*} that minimizes the total transport cost KP(\mu,\nu,c)=\inf_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}c(x,y)\,d\pi(x,y). (4) The integral can be written as \mathbb{E}[c(\xi,\eta)], where (\xi,\eta)\sim\pi . A plan \pi^{*} at which the minimum is attained is called an optimal transport plan . Under assumptions above 4 4 4 For unbounded domain additionally c(x,y)\leq a(x)+b(y) for some integrable functions a\in L_{1}(\mu) and b\in L_{1}(\nu). the infimum in ( 4 ) is actually attained ( 36 , Theorem 5.10 (iii)) . 2.4 Dual Problem Problem ( 4 ) can be reformulated as a maximization problem (for generality we write supremum, but it is attained under very general assumptions: DP(\mu,\nu,c)=\underset{\begin{subarray}{c}\varphi\in C(X),\psi\in C(Y)\\ \varphi(x)+\psi(y)\leq c(x,y)\end{subarray}}{\sup}\left(\int\limits_{X}\varphi d\mu+\int\limits_{Y}\psi d\nu\right) (5) where X and Y are compact sets, in general case \varphi and \psi should be absolutely integrable. Under our assumptions (see, e.g., ( 36 , Theorem 5.10 (iii)) ), DP(\mu,\nu,c)=KP(\mu,\nu,c). 2.5 Semi-Dual Problem For functions \varphi\colon X\to\mathbb{R}\cup\{\pm\infty\} and \psi\colon Y\to\mathbb{R}\cup\{\pm\infty\} define c -transform \varphi^{c}(y)=\underset{x\in X}{\inf}[c(x,y)-\varphi(x)],\qquad\psi^{c}(x)=\underset{y\in Y}{\inf}[c(x,y)-\psi(y)]. (6) A function \varphi(x) is said to be c -concave, if there exists a function \psi(y), such that \varphi(x)=\psi^{c}(x). For X and Y bounded subsets in \mathbb{R}^{n} the dual problem of optimal transport can be formulated as semi-dual (see): 5 5 5 For unbounded domains, we should assume \psi\in L_{1}(d\nu). SDP(\mu,\nu,c)=\sup_{\psi\in C(Y)}\left(\int_{X}\psi^{c}(x)\,d\mu+\int_{Y}\psi(y)\,d\nu\right). (7) 2.6 Connection between the Monge and Kantorovich Problems The following theorem establishes the relation between the Monge and Kantorovich formulations of optimal transport. Theorem 1 ( 26 ) . Let X and Y be Polish spaces and let \mu\in\mathcal{P}(X) and \nu\in\mathcal{P}(Y) be probability measures. Assume that \mu is nonatomic and that the cost function c:X\times Y\to[0,\infty) is continuous. Then MP(\mu,\nu,c)=KP(\mu,\nu,c). The theorem states that the infimum value of the Monge problem coincides with the minimum value of the Kantorovich problem. In particular, although the Monge problem may fail to admit a minimizing map, it is possible to approximate the optimal transport plan by transport maps whenever the source measure is nonatomic. In Table 1 , we summarize the theoretical results on the existence of the optimal transport map according to 2 . Table 1 : Existence and equivalence properties in optimal transport under different assumptions. \mu,\nu c(x,y) \pi^{\star} \varphi^{\star},\psi^{\star} T^{\star} KP=DP KP=MP general continuous