Regularized Unbalanced Optimal Transport with Pearson Marginal Penalties

arXiv:2503.15105v5 Announce Type: replace-cross Abstract: We study quadratically regularized unbalanced optimal transport with Pearson marginal penalties and a lower bound $\delta\ge0$ on the plan, including the sparse case $\delta=0$. We organize the analysis around the active interface, where the plan switches from its lower bound to larger values. We prove a Newton remainder estimate that depends linearly on the marginal measure of the boundary layer around this interface, and a maximum-norm inverse estimate uniform over all Newton derivatives and cell volumes. Together they give local superlinear convergence of semismooth Newton iteration in function space, of q-order at least $1+\alpha$ when the boundary-layer measure is $O(t^\alpha)$, and a common convergence neighborhood along each refinement sequence whose data converge uniformly. Transverse interfaces give second-order supercloseness of the discrete potentials to the cell averages of the continuum potentials. A directional curvature condition on the input data verifies the interface condition before the solution is known and yields an explicit Newton convergence radius on all sufficiently fine meshes, uniformly in the lower bound. A globalized inexact semismooth Newton iteration has mesh-independent numbers of outer iterations and of full-array operations, that is, passes over the plan array. Its output satisfies an a posteriori error bound relative to the continuum optimal plan. Experiments test the rates at transverse interfaces and at interfaces with tangencies, the curvature criterion, and the algorithmic work. All estimates hold for a fixed regularization parameter and a fixed lower bound on the densities.

Abstract:We study quadratically regularized unbalanced optimal transport with Pearson marginal penalties and a lower bound $\delta\ge0$ on the plan, including the sparse case $\delta=0$. We organize the analysis around the active interface, where the plan switches from its lower bound to larger values. We prove a Newton remainder estimate that depends linearly on the marginal measure of the boundary layer around this interface, and a maximum-norm inverse estimate uniform over all Newton derivatives and cell volumes. Together they give local superlinear convergence of semismooth Newton iteration in function space, of q-order at least $1+\alpha$ when the boundary-layer measure is $O(t^\alpha)$, and a common convergence neighborhood along each refinement sequence whose data converge uniformly. Transverse interfaces give second-order supercloseness of the discrete potentials to the cell averages of the continuum potentials. A directional curvature condition on the input data verifies the interface condition before the solution is known and yields an explicit Newton convergence radius on all sufficiently fine meshes, uniformly in the lower bound. A globalized inexact semismooth Newton iteration has mesh-independent numbers of outer iterations and of full-array operations, that is, passes over the plan array. Its output satisfies an a posteriori error bound relative to the continuum optimal plan. Experiments test the rates at transverse interfaces and at interfaces with tangencies, the curvature criterion, and the algorithmic work. All estimates hold for a fixed regularization parameter and a fixed lower bound on the densities.

The paper is a more focused version of the previous one "Control, Optimal Transport and a Sinkhorn-inspired algorithm for Neural Differential Equations". In this version, we focus on the UOT scheme with Pearson penalties, that is, we provide a much deeper analysis, and leave the other contents out for deeper studies in the future

Numerical Analysis (math.NA); Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2503.15105 [math.NA]

(or arXiv:2503.15105v5 [math.NA] for this version)

Off-topic for aiqbench

Regularized Unbalanced Optimal Transport with Pearson Marginal Penalties

Related coverage