Source-linked AI summary
Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
Guillaume Carlier, Vincent Duval, Gabriel Peyré, Bernhard Schmitzer
TL;DR
The paper addresses the computational cost of optimal transport and related gradient-flow schemes. It proves convergence for entropy-regularized OT and for entropically smoothed JKO flows under a controlled joint limit. The analysis also identifies scope boundaries in the numerical examples and the required rate between smoothing and time-step parameters.
Problem
Optimal transport and Wasserstein gradient-flow steps can be computationally challenging because they require solving convex or linear programs, motivating efficiently computable entropic proxies.
Method
The paper analyzes entropy-regularized OT through Γ-convergence and studies an entropically smoothed JKO scheme using KL-projection-based discretization and Dykstra’s algorithm.
Results
Γ-convergence holds for squared-Euclidean entropic OT, while discrete entropic JKO flows converge when step size and smoothing strength vanish in a suitable joint limit.
Takeaways & Limitations
Entropic regularization can approximate OT transport plans and gradient flows while retaining computationally parallelizable schemes, provided the smoothing vanishes sufficiently relative to the time step.
Takeaways & Limitations
Numerical gradient-flow artifacts become prohibitive and the scheme freezes at low spatial resolution, while the congestion-constraint example is outside the convergence analysis.
Abstract
from arXiv · showhide
Replacing positivity constraints by an entropy barrier is popular to approximate solutions of linear programs. In the special case of the optimal transport problem, this technique dates back to the early work of Schrödinger. This approach has recently been used successfully to solve optimal transport related problems in several applied fields such as imaging sciences, machine learning and social sciences. The main reason for this success is that, in contrast to linear programming solvers, the resulting algorithms are highly parallelizable and take advantage of the geometry of the computational grid (e.g. an image or a triangulated mesh). The first contribution of this article is the proof of the $Γ$-convergence of the entropic regularized optimal transport problem towards the Monge-Kantorovich problem for the squared Euclidean norm cost function. This implies in particular the convergence of the optimal entropic regularized transport plan towards an optimal transport plan as the entropy vanishes. Optimal transport distances are also useful to define gradient flows as a limit of implicit Euler steps according to the transportation distance. Our second contribution is a proof that implicit steps according to the entropic regularized distance converge towards the original gradient flow when both the step size and the entropic penalty vanish (in some controlled way).
1. Introduction.
Optimal transport is powerful but computationally demanding, motivating entropic regularization as a parallelizable, geometry-aware alternative for transport problems and gradient flows. The paper proves convergence of entropic OT and of entropically smoothed gradient-flow schemes under controlled vanishing limits.
- OT solves broad theoretical and practical problems but requires a linear program over distributions on a product space, making computation costly.
- 1.1. Motivation.: Entropic regularization replaces positivity constraints with an entropy barrier and offers proxies for OT distances and transport plans with better computational complexity than traditional linear-programming solvers.
- 1.2. Related Work.: Alternating KL projections reduce to closed-form diagonal scaling, yielding Sinkhorn’s algorithm and enabling parallel implementations.
- 1.2. Related Work.: Entropic regularization extends beyond Kantorovich OT to Wasserstein barycenters and other transport-like linear programs, including partial transport.
- 1.2. Related Work.: The studied entropic JKO scheme replaces the Wasserstein distance with an entropy-smoothed approximation and uses Dykstra’s algorithm for large grids and meshed surfaces.
- 1.2. Related Work.: The paper proves Γ-convergence of entropic OT for squared Euclidean cost and convergence of entropically smoothed JKO flows when smoothing and step size vanish jointly.
2. Entropy Regularized Optimal Transport.
The section develops entropy-regularized optimal transport and proves its convergence to classical optimal transport as the regularization vanishes. It also establishes convergence of optimal plans and applies the framework to Wasserstein barycenters.
- Set-up: Entropy regularization adds an ε-scaled entropy term to the Kantorovich transport-cost minimization over couplings.The regularized functional is finite on admissible couplings and infinite otherwise.
- Preliminary Results: For finite-entropy marginals, an entropy-regularized minimizing coupling exists.The proof uses tightness, narrow compactness, and lower semicontinuity of transport cost and entropy.
- Γ-convergence: Under uniqueness of the unregularized optimal plan, the regularized transport values and optimal plans converge to their classical counterparts.The argument uses equicoercivity and uniqueness of the optimal transport plan.
- Γ-convergence: The entropy-regularized functionals Γ-converge to the unregularized transport functional in the narrow topology as ε vanishes.The proof combines liminf and recovery-sequence constructions, using block approximations of transport plans.
- Application to Wasserstein Barycenters: Wasserstein barycenters arise as common second marginals of optimal couplings, and their entropic functionals also admit minimizers and Γ-converge to the unregularized functional.The barycenter formulation optimizes over couplings sharing a common, non-fixed second marginal.
3. Entropy Regularized Wasserstein Gradient Flows.
The section studies a time-discrete gradient descent scheme that replaces the Wasserstein distance with its entropy-regularized variant. It proves convergence to the same PDE as the unregularized scheme when entropy and time-step parameters vanish jointly.
- Entropy Regularized Wasserstein Gradient Flows: The scheme replaces the standard optimal transport distance in the JKO implicit Euler method with an entropy-regularized variant.The regularized quantity is not itself a distance.
- Entropy Regularized Wasserstein Gradient Flows: When entropy regularization and the time-step size vanish in a suitable joint limit, the discrete scheme converges to the same PDE as the unregularized scheme.The section frames this as convergence of the entropy-regularized gradient-flow discretization.
3.1. Set-up.
The section formulates an entropically regularized JKO scheme for gradient flows, replacing the Wasserstein term with a smoothed transport cost and relating entropy strength to the time step. Under suitable assumptions on the free energy, the interpolated scheme converges when ε|log(ε)|=O(τ^2).
- Set-up: The scheme addresses how entropy regularization ε and time step τ can jointly vanish while preserving convergence to the evolution equation.The regularized Euler scheme contains both parameters, so their asymptotic relation is central.
- Set-up: The regularized JKO step minimizes 1/(2τ) W_ε^2(µ,ν)+F(ν), where ε controls entropy smoothing and F is the free energy.F describes external potentials and local self-interactions.
- Set-up: The free-energy assumptions require a nonnegative Lipschitz potential density and a convex, twice-differentiable, super-linear internal energy density.These assumptions define the class of energies considered in the analysis.
- Set-up: The regularized iterates are constructed recursively from an initial density with finite free energy, then represented by a piecewise-constant time interpolation.The interpolation assigns ρ(ε,τ,k) to each interval [kτ,(k+1)τ).
- Set-up: ε|log(ε)|=O(τ^2) guarantees convergence of the regularized scheme to a solution of the target PDE, while ε=o(τ) is necessary.The paper does not establish optimality of the stronger condition.
3.2. Preliminary Results.
The preliminary analysis establishes lower semicontinuity, existence, and uniqueness properties for the regularized JKO minimization problem. These results rely on entropy and moment bounds that provide compactness for minimizing sequences.
- Preliminary Results: F is narrowly lower semicontinuous under bounded second-order moments.The result follows separately for potential and internal energies under the stated assumptions.
- Preliminary Results: The regularized JKO functional has a unique minimizer.The surrounding argument uses entropy bounds and convexity of F.
- Preliminary Results: Entropy and second-moment bounds make minimizing sequences tight, enabling extraction of a narrowly convergent subsequence.Lower semicontinuity preserves the relevant bounds in the limit.
- Preliminary Results: The first variation of F is analyzed along smooth flows generated by compactly supported vector fields.This prepares the Euler-Lagrange analysis for the regularized minimizer.
3.3. Euler-Lagrange Equations.
This section derives the Euler-Lagrange relation for a minimizer of the regularized JKO functional by varying the density along smooth flows. The free-energy variation includes internal-energy pressure and potential-energy contributions.
- Euler-Lagrange Equations: The first variation of F along a smooth flow is computed using the flow Jacobian and dominated convergence.The internal-energy contribution is expressed through the pressure p, while the potential term is treated analogously.
- Euler-Lagrange Equations: The Euler-Lagrange equation combines the optimal transport plan for W_ε with the first variation δF(ν,w).It characterizes the optimizer of J_ε,τ(µ,·).
- Euler-Lagrange Equations: A coupling obtained by pushing an optimal transport plan through the smooth flow provides an upper bound for the perturbed transport cost.This estimate supplies the transport-side variation used in the limiting argument.
- Euler-Lagrange Equations: Linearity in the vector field and simultaneous validity for w and −w turn the variational inequality into equality.This identifies the exact first-order condition.
3.4. A Priori Estimates.
The a priori analysis controls entropy, free energy, moments, and cumulative transport movement across the regularized iterates. These estimates provide the compactness needed to pass to the limit in the Euler-Lagrange equation.
- A Priori Estimates: The smoothing construction bounds the regularized step through entropy, free-energy, and transport terms after choosing σ=√ε.The mollified competitor satisfies F(ρ̂)≤F(ρ(k))+Cσ.
- A Priori Estimates: Proposition 3.8 gives a uniform second-moment bound for all steps with τN≤T and ε satisfying the parameter condition.The bound is uniform over admissible parameter pairs and iterations.
- A Priori Estimates: The cumulative Wasserstein displacement between iterates is controlled by the sum of the individual step distances.The estimate uses the triangle and Cauchy-Schwarz inequalities.
- A Priori Estimates: Summed step estimates yield uniform lower entropy bounds, upper negative-entropy bounds, and lower free-energy bounds for every iterate.These bounds are recorded in Corollary 3.9.
- A Priori Estimates: The resulting estimates are roughly the same as for the standard JKO scheme and provide sufficient compactness for the limiting Euler-Lagrange analysis.This connects the a priori bounds to the convergence proof.
3.5. Convergence.
The section establishes compactness and convergence for interpolated regularized flows as the regularization and time-step parameters vanish under the prescribed scaling. It also identifies the functional-analytic properties needed to obtain strong convergence.
- Uniform estimates: Under the prescribed parameter relation, the interpolated family P(ε,τ,N) satisfies uniform estimates independent of N, ε, and τ.The estimates are obtained by combining results from earlier sections and summing over time steps.
- Regularity: The auxiliary quantity µ(k) = ε/(2τ)ρ(k) + p(ρ(k)) belongs to W 1,1(Rn), using the Euler–Lagrange equation and transport-plan disintegration.Its integrability follows from finite energy and second-moment bounds, while the distributional derivative is represented by integration.
- Convergence: After a suitable subsequence, P(ε,τ,N) converges strongly in Lm((0,T) × Rn) to a limit curve P.The strong convergence relies on a generalized Aubin–Lions theorem together with BV estimates and compact sub-level sets.
- Convergence: The associated pressures converge strongly in L1((0,T) × Rn), by continuity of the pressure mapping from Lm to L1.The pressure convergence uses the growth assumption p(s) ≤ C·s^m.
- Compactness: G is lower semi-continuous in Lm(Rn), and its sub-level sets are compact.The proof uses BV bounds, local L1 compactness, and control of mass outside large balls.
3.6. Convergence to the Nonlinear Diffusion PDE.
The section proves that limits of regularized JKO interpolations solve the target nonlinear diffusion evolution equation. The argument passes to the limit in a weak formulation using strong convergence and vanishing discretization errors.
- Convergence: The discrete interpolations Pk converge strongly in Lm, their pressures converge strongly in L1, and time slices converge narrowly uniformly in time.These convergences provide the compactness needed for the limiting weak formulation.
- Theorem: Theorem 3.16 states that the limit curve of measures P solves the nonlinear diffusion evolution equation.The theorem applies under Assumption 3.1 and condition (3.57).
- Limit passage: Taylor expansion of the test function separates the transport increment into a first-order term and a controlled remainder.The remainder is bounded using the time step and transport estimates.
- Limit passage: The Euler–Lagrange equation rewrites the first-order transport term using the pressure and drift contributions.The equation is tested with the spatial gradient of the smooth test function.
- Conclusion: Because the error terms vanish and the strong convergences pass the remaining terms to the limit, the resulting identity is precisely the weak form of the target equation.Every cluster point is a solution; if the target equation is unique, the full sequence converges rather than only a subsequence.
- Numerics: Numerical simulations in one and two dimensions illustrate the behavior of entropic regularization and its small-ε limit.The section recalls a numerical scheme proposed earlier and later refined.
4. Numerical Illustrations.
Numerical experiments evaluate entropic JKO schemes for heat, porous media, drift, potential, and congestion models, comparing them with analytic behavior and examining discretization effects. The results show convergence trends, controlled deviations from exact solutions, and model-specific dynamics.
- Numerical method: The entropic JKO step becomes a finite-dimensional convex program whose transport solution has Gibbs-kernel scaling form and can be computed by generalized Sinkhorn iterations.The Gibbs kernel is K_i,j = exp(−c_i,j/ε) · l^2, and proximal maps for the model energies can be closed-form or tabulated.
- Numerical setup: The computations discretize [0, 1]^n on Cartesian grids with p = 1024 points in one dimension or 256 × 256 points in two dimensions.The schemes use discrete measures supported on uniform grid points representing equal volume elements.
- Comparison with analytic solutions: For ε = 10^-4, entropic smoothing causes visible blurring, while this effect is virtually invisible for ε = 10^-6 and compact support is well preserved.For m = 10, time discretization additionally struggles with rapid early changes when the density is concentrated; agreement improves near steady state.
- Error analysis: For fixed τ, the L1 error decreases as ε approaches zero, while larger τ produces zigzagged interpolation and poorer resolution of rapid early-time changes.The reported comparisons concern the porous media equation with m = 2 and time slices against the predicted solution.
- Model-specific dynamics: The simulations reproduce drift, pressure-driven spreading, and congestion behavior, including preserved compact support and prevention of collapse into a Dirac mass.The congestion experiment uses u(s) = 0 on [0, 1] and u(s) = +∞ otherwise, which is not covered by the convergence analysis but is studied numerically.