Computing Optimal Transport Plans via Min-Max Gradient Flows

Lauren Conger a,, Franca Hoffmann b,, Ricardo Baptista c,, Eric Mazumdar d, · 2025

Read Computing Optimal Transport Plans via Min-Max Gradient Flows by Lauren Conger a,, Franca Hoffmann b,, Ricardo Baptista c,, Eric Mazumdar d, (2025) 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-2504-16890.txt.

Introduction

Lauren Conger and co-authors wrote a paper in 2025 on a game-like method for computing optimal transport plans. Optimal transport is a classic problem: how to move goods to where they are needed at the least total cost. The problem can be posed as a game between two players. One player picks the transport plan. The other prices each route.

At the point where neither player can gain by changing strategy, the plan is the optimal one. The team shows that paired gradient flows, run at separated timescales, converge to that optimal plan. Their implementation uses a particle method, in which a swarm of particles stands for the piles of goods. The constraints on the plan are enforced weakly, using a divergence score that tunes its own weight as the run proceeds. Tests compare the standard and reversed forms of that score, highlighting the advantages of each.

Catalog record

CREATORLauren Conger a,, Franca Hoffmann b,, Ricardo Baptista c,, Eric Mazumdar d,
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16890

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computing Optimal Transport Plans via Min-Max Gradient Flows Lauren Conger a,, Franca Hoffmann b,, Ricardo Baptista c,, Eric Mazumdar d, Abstract We pose the Kantorovich optimal transport problem as a min-max problem with a Nash equilibrium that can be obtained dynamically via a two-player game, providing a framework for approximating optimal couplings. We prove convergence of the timescale-separated gradient descent dynamics to the optimal transport plan, and implement the gradient descent algorithm with a particle method, where the marginal constraints are enforced weakly using the KL divergence, automatically selecting a dynamical adaptation of the regularizer. The numerical results highlight the different advantages of using the standard Kullback-Leibler (KL) divergence versus the reverse KL divergence with this approach, opening the door for new methodologies. Keywords. optimal transport, Wasserstein gradient flow, min-max 1 Introduction Optimally transporting mass from one distribution \mu to another \nu is an important problem in many applications, ranging from sampling to numerically solving partial differential equations. In this work, we reformulate the Kantorovich optimal transport (OT) problem \displaystyle\inf_{\rho\in\Gamma(\mu,\nu)}\iint c(x,y)\mathrm{d}\rho(x,y)\,, as a min-max problem by rewriting the marginal constraints with KL divergences, the weight of which is maximized, \displaystyle\inf_{\rho}\sup_{\Lambda\in\mathbb{R}}\iint c(x,y)\mathrm{d}\rho(x,y)+\Lambda\left(\text{KL}(\rho_{1}\,|\,\mu)+\text{KL}(\rho_{2}\,|\,\nu)\right)\,. In the above, \Gamma(\mu,\nu) is the set of measures whose marginals are \mu and \nu , the function c denotes the optimal transport cost, and \rho_{1} and \rho_{2} are the marginals of the joint probability measure \rho . The Nash equilibrium of the min-max problem coincides with the minimizer of the OT problem, and this formulation allows us to develop a gradient flow particle method to dynamically approximate the optimal coupling. Other works have proposed particle methods for solving OT problems, such as [ 17 ] , which presents a finite-particle method for mass transport problems in the \mathscr{W} metric, applied to particles diffusing on a sphere. Prior to that, [ 16 ] proposed a particle method for computing OT plans, and we build upon their numerical method by using a different, more efficient density estimation method and more advantageous particle initializations. [ 16 ] provides a \Gamma -convergence result that we extend to achieve a Danskin-type theorem (also known as the envelope theorem) for the best-response of the coupling to the soft constraint, when considering the min-max dynamics under timescale separation. We address an open question posed in that paper by proving that the energy functional is displacement convex, leading to gradient flow convergence guarantees. Viewing the OT problem through the lens of a min-max flow in infinite dimensions allows us to build upon the results in [ 8 ] , which provides conditions under which convergence of the min-max dynamics in the space of measures holds. In our setting, the energy functional defining the zero-sum game is no longer strongly convex in both players (with one player being the transport plan, and the other player being the regularization parameter enforcing the marginal constraints), and the estimates we prove here provide new results in this setting. The most popular and best-developed method for computing OT plans is the Sinkhorn algorithm [ 9 ] . Our particle method is not expected to outperform state-of-the-art implementations of the Sinkhorn algorithm in computation time—due in large part to the amount of recent work on numerically tuning the Sinkhorn algorithm for better performance [ 1 , 14 ] . The key contributions of our method in comparison to Sinkhorn lies in the greater expressivity of our approximation to the optimal coupling. The Sinkhorn algorithm is a reweighting of points which approximate a probability density, which means the joint distribution achieved is constrained to have support on the samples from the input marginals. Because we use particles instead, we can construct joint distributions with different support than the samples from the target marginals, which is expected to yield more expressivity especially in high dimensions. Further, the entropy regularization term in the Sinkhorn algorithm encourages a joint density which factorizes with increasing regularization, but ours does not, allowing for the possibility of obtaining a solution closer to the true optimal plan, while still maintaining the computational benefits of regularization. Recent works have explored the connection between the Sinkhorn algorithm and Wasserstein-2 gradient flows, including [ 12 ] , which develops a continuous time Sinkhorn flow, encompassing the setting of [ 10 ] , which formulates the notion of Sinkhorn as a Wasserstein-2 mirror descent and provides convergence results. [ 7 ] gives conditions on the cost function for exponential convergence of the dual sub-optimality gap for population-level Sinkhorn. Our work is complimentary in that we do not have the KL regularization term which encourages factorization, but we do have a KL penalty term on the marginals which, when taken to have infinite weight, enforces the marginal constraints exactly and guarantees convergence of the energy to the true optimal cost. Other approaches for approximating the OT plan exist, with a vast literature. Alternative parametric methods learn potential functions in the OT problem, which define a parametric approximation to the transport plan [ 21 , 13 ] . Works which compute OT maps using the Benamou-Brenier formulation of the Wasserstein-2 distance include [ 18 ] , which provides a proximal splitting algorithm, and shows equivalence with the alternating direction method of multipliers. Similarly, [ 15 ] solves the discretized Schrödinger’s bridge problem and [ 5 ] provides a method for discretizing a gradient flow in time and solves the resulting subproblems in a way that could instead be applied to an OT problem with the Benamou-Brenier formulation. Our particle method and corresponding theoretical results take the approach of relaxing both marginal constraints simultaneously with convergence guarantees as the constraints are more tightly enforced. Contributions: We pose the optimal transport problem as a min-max problem, allowing us to prove convergence of a timescale-separated min-max flow to the optimal transport plan, in infinite dimensions. To do so we draw on ideas and make connections to singularly perturbed dynamical systems and two-timescale dynamics [ 20 ] . In particular, we generalize ideas from that literature to infinite dimensions. Along the way, we address an open question in [ 16 ] by proving displacement convexity of the energy functional and convergence of the resulting gradient flow to the minimizer. Our analysis allows us to derive a new particle-based method for approximating optimal transport plans that has convergence guarantees and which could ultimately be a powerful tool in the optimal transport toolbox. Numerically, we illustrate how the L^{2} marginal density error can be improved if the shape of the source and target are taken into account when selecting forward KL (mode-seeking) vs reverse KL (moment-matching) for the energy functional when enforcing the soft constraints on the marginals. 2 Problem Setup 2.1 Notation Let \mathcal{P}_{2}(\mathbb{R}^{d}) denote the space of probability measures with finite second moments on \mathbb{R}^{d} . We use the notation \rho(x)\mathrm{d}x for measures with or without Lebesgue density. For two measures \mu\in\mathcal{P}(\mathbb{R}^{d_{x}}) and \nu\in\mathcal{P}(\mathbb{R}^{d_{y}}) , we denote by \Gamma(\mu,\nu) the set of all joint distributions whose marginals are equal to \mu and \nu , i.e., \displaystyle\Gamma(\mu,\nu)=\left\{\gamma\in\mathcal{P}(\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}})\,|\,\mu=\pi_{1\#}\gamma\,,\,\nu=\pi_{2\#}\gamma\right\}, where \pi_{i\#}\gamma denotes the pushforward of \gamma on the i^{th} marginal. The transport cost function is c:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to[0,\infty) , and if c(x,y)=\|x-y\|^{2} is the quadratic cost, we denote the corresponding Wasserstein metric by \mathscr{W} ,

Read the complete text