🔢 mathematics

Stability of the Monge Map in Semi-Dual Optimal Transport

This paper establishes that the semi-dual optimal transport problem possesses a degenerate saddle-point structure equivalent to a constrained optimization problem, and derives necessary and sufficient conditions for Monge map convergence that explain why numerical algorithms typically require more iterations to update the transport map than the potential.

Original authors: Anton Selitskiy, David Millard

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anton Selitskiy, David Millard

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Moving Mountains of Data

Imagine you have a pile of sand (Source) and a specific mold you want to shape it into (Target). Your goal is to move every grain of sand from the pile to the mold using the least amount of energy possible. In the world of math and machine learning, this is called Optimal Transport.

For a long time, researchers have used a specific mathematical recipe (called the "Semi-Dual" formulation) to teach computers how to do this moving job. They use two "neural networks" (computer brains) to figure it out:

The Mover (Transport Map): Decides where each grain of sand goes.
The Judge (Potential): Checks if the sand ended up in the right shape and penalizes bad moves.

The Problem: The "Flat" Trap

The authors of this paper discovered a hidden flaw in how these two networks interact. They found that the mathematical landscape they are climbing looks like a flat plateau rather than a sharp mountain peak.

The Analogy:
Imagine you are trying to find the highest point on a mountain (the perfect solution).

The Old Belief: Everyone thought that to find the peak, you had to climb the mountain and find the perfect compass direction (the optimal "Judge" or potential) at the same time. If your compass was slightly off, you wouldn't reach the top.
The New Discovery: The authors found that once the "Mover" gets close to the right path, the "Judge" stops mattering. The mountain becomes a flat table. No matter which way the Judge points, the score stays the same.

This is called a degenerate saddle-point. It means the "Judge" can keep spinning its wheels, changing wildly, while the "Mover" is actually doing a great job. The math says the Judge should be perfect, but the reality is that the Mover can be perfect even if the Judge is confused.

Why This Matters for Training

This explains a confusing habit that computer scientists have noticed for years: They have to update the "Mover" many more times than the "Judge" to get good results.

The Analogy:
Think of a dance partner.

If the "Judge" (the music) is changing too fast, the "Mover" (the dancer) can't keep up.
The paper explains that because the "Judge" doesn't actually need to be perfect to get a good score (thanks to that flat plateau), you should let the "Mover" do most of the work. You let the dancer practice their steps (update the Mover) many times, while only occasionally checking the music (updating the Judge).

If you try to update them equally, the system gets unstable because the Judge is chasing a ghost that doesn't exist anymore.

The New Rulebook (The Main Result)

The authors wrote a new formula to measure how good the "Mover" is.

Old Way: "Is the Mover good? Only if the Judge is also perfect."
New Way: "Is the Mover good? We can tell just by looking at how much energy it took to move the sand and how close the final shape is to the target. We don't need to check if the Judge is perfect."

This is a big deal because it proves that in practice, you can have a perfect transport map even if the potential (the Judge) is nowhere near optimal.

Summary of Key Takeaways

The "Flat" Phenomenon: Once the transport map is close to the solution, the objective function becomes "flat" regarding the potential. The potential can change without changing the score.
Two-Speed Training: This explains why algorithms work best when they update the transport map (the mover) frequently and the potential (the judge) slowly. It's a "two-timescale" system.
Better Convergence Checks: You don't need to wait for the potential to converge to know if your transport map is working. You can measure the map's success directly.
Warning for Researchers: Many previous papers assumed that if the math looks good, both the map and the potential must be optimal. This paper says: "Not necessarily." The map can be right while the potential is wrong.

What This Paper Does NOT Say

It does not invent a new medical treatment or clinical tool.
It does not claim this solves all machine learning problems.
It does not say you should stop using "Judeges" (potentials); it just says they behave differently than we thought when the "Mover" is doing its job well.

In short, the paper fixes the theory behind how we train these AI models, explaining why the "Mover" needs to do the heavy lifting while the "Judge" can take a back seat once the work is nearly done.

Technical Summary: Stability of the Monge Map in Semi-Dual Optimal Transport

Problem Statement
Optimal Transport (OT) has become a foundational tool in machine learning, underpinning generative models such as GANs, VAEs, and diffusion models. A significant class of algorithms, including Neural Optimal Transport (NOT), relies on the semi-dual formulation of the OT problem combined with amortized optimization. While these methods exploit the existence and uniqueness of optimal transport maps (Monge maps) under specific conditions, they often lack rigorous convergence guarantees for the learned maps. Existing literature frequently assumes the existence of an optimal map and the well-posedness of the optimization problem, yet these assumptions can fail in practice. Furthermore, empirical observations suggest that numerical algorithms often require significantly more iterations to update the transport map ( $t$ ) than the dual potential ( $\psi$ ), a phenomenon previously lacking a theoretical explanation.

Methodology and Theoretical Framework
The authors analyze the semi-dual formulation of the OT problem, specifically focusing on the saddle-point structure of the objective functional. The study assumes $X$ and $Y$ are compact subsets of $\mathbb{R}^n$ with probability measures $\mu$ and $\nu$ that are absolutely continuous with respect to the Lebesgue measure.

Saddle-Point Analysis: The paper reformulates the semi-dual problem as a minimax problem involving a transport map $t$ and a potential $\psi$ . The objective functional is defined as:
$F(\psi, t) = \int_X c(x, t(x)) d\mu + \int_Y \psi(y) d(\nu - t_\sharp \mu)$
The authors demonstrate that this formulation possesses a degenerate saddle-point structure. Specifically, at the optimal transport map $T^\star$ , the value of the functional $F(\psi, T^\star)$ becomes independent of the potential $\psi$ . This "flatness" implies that once the transport map is near optimal, the potential $\psi$ is no longer uniquely determined by the objective, even if the map is not yet perfectly optimal.
Convergence Conditions: Unlike previous works that rely on the optimality of the dual potential to prove map convergence, this paper derives necessary and sufficient conditions for the convergence of Monge maps that do not require $\psi$ to be optimal. The authors establish an error bound for the transport map $t$ in the $L^2$ norm:
$\|t - T^\star\|_{L^2}^2 \lesssim |F(t, \psi) - W_2(\mu, \nu)^2| + d_{KR}(t_\sharp \mu, \nu)$
This estimate shows that the distance to the optimal map depends on the gap in the objective value and the Kantorovich-Rubinstein distance between the push-forward measure and the target, rather than the proximity of $\psi$ to the optimal potential.
Dynamical Systems Interpretation: The paper interprets the training dynamics of NOT algorithms as a continuous-time two-timescale dynamical system. The analysis reveals that the constraint $t_\sharp \mu = \nu$ is not satisfied during intermediate training steps, causing the maximization over $\psi$ to be unbounded without a restoring force. To stabilize the system, the primal variable $t$ must evolve on a faster timescale than the dual variable $\psi$ . This provides a theoretical justification for the empirical practice of performing multiple gradient descent steps on the transport map for every single gradient ascent step on the potential.

Key Contributions and Results

Identification of Degeneracy: The paper explicitly identifies the degenerate saddle-point structure in the semi-dual OT formulation, where the objective becomes independent of the potential at the optimal map. This explains why the potential may diverge or fail to converge even as the transport map converges.
Convergence Estimate Independent of Potential: The authors provide a convergence estimate (Equation 17) that bounds the error of the transport map without assuming the optimality of the dual potential. This challenges previous assumptions in the literature that link map convergence directly to potential convergence.
Explanation of Two-Timescale Updates: The paper theoretically validates the "two-timescale" update rule used in NOT and related WGAN formulations. It demonstrates that updating the map $t$ multiple times per potential update ( $K \eta_t / \eta_\psi$ ) is necessary to stabilize the system and reduce constraint violations before the potential is updated.
Experimental Validation: Numerical experiments on Gaussian distributions confirm that the transport map can converge to the optimal solution while the potential remains far from optimal. The results show that the ratio of update steps ( $K$ ) and learning rates ( $\eta_t/\eta_\psi$ ) critically affects whether the map or the potential is learned more accurately.

Significance and Claims
The paper claims to provide a theoretical explanation for the practical behavior of neural optimal transport algorithms, specifically why they often require more iterations for the map than the potential. By characterizing the semi-dual problem as a constrained optimization task with a degenerate saddle point, the authors clarify why standard convergence guarantees based on potential optimality are insufficient.

The authors emphasize that the existence of an infimum in the semi-dual problem does not guarantee the existence of a minimizer for the potential, a distinction that has led to incorrect claims in prior literature. They argue that "spurious solutions" and gradient deviations observed in practice arise from this degeneracy, where different potentials yield distinct gradients near the optimal map. Consequently, the paper suggests that imposing structural constraints (like convexity) on the potential may reduce degeneracy but introduces approximation bias, while unconstrained parameterizations may perform better despite the lack of strict saddle-point properties.

The work concludes that the stability of the Monge map in semi-dual OT is contingent on the relative timescales of the map and potential updates, and that convergence of the map does not imply convergence of the potential.