math.NAMar 19, 2025

Regularized Unbalanced Optimal Transport with Pearson Marginal Penalties

Authors: Minh-Nhat Phung, Minh-Binh Tran

Abstract

We study quadratically regularized unbalanced optimal transport with Pearson marginal penalties and a lower bound δ≥0δ\ge0 on the plan, including the sparse case δ=0δ=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+α1+α when the boundary-layer measure is O(tα)O(t^α), 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.

Explore similar work

May 7, 2026

Stability of the Monge Map in Semi-Dual Optimal Transport

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.
Sep 30, 2026

Accelerated Algorithm for Sparse Regularized Partial Optimal Transport

Partial Optimal Transport (POT) extends the classical optimal transport problem by relaxing the strict mass conservation constraint, enabling its use in a wide range of real-world applications. In many of these settings, sparse transport plans are preferred for their interpretability and computational benefits. While smooth and strongly convex regularizers - such as quadratic or elastic net - have been vastly used in various machine learning applications to induce sparsity and accelerate computation, they have received less algorithmic attention compared to entropic approaches for computational POT. In this paper, we propose a new optimization framework that leverages these regularizers through a penalty-based reformulation, enabling efficient gradient-based updates while preserving the structure of the original problem. Our method accommodates a broad class of regularizers that promote structured and sparse transport plans. Building on this formulation, we design an accelerated first-order algorithm that alternates between smooth updates and simple projection steps. Through empirical benchmarks on color transfer, domain adaptation, and point cloud registration, our approach consistently outperforms established baselines - achieving lower transport cost, higher sparsity, and faster convergence - making it a practical and scalable solution for modern transport problems.
Sep 27, 2026

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory

We characterize Bregman Douglas-Rachford splitting (BDRS) for unregularized discrete optimal transport and develop an anytime primal-dual certificate in linear memory. We first establish that BDRS coincides with warm-started Inexact Proximal point method for exact Optimal Transport (IPOT) using a single inner Sinkhorn iteration. By eliminating the primal transport plan from the updates, we derive an equivalent dual formulation that reveals BDRS as annealed Sinkhorn under an implicit inverse-linear temperature schedule, with an additional log-scaling momentum term and a cooler kernel. While this explains the role of the temperature parameter in BDRS as an initial temperature, it also reduces the solver's memory requirement from quadratic to linear. Utilizing this annealing perspective, we introduce overrelaxed BDRS, which combines annealing and overrelaxed scaling within a single recursion. We derive a primal-dual certificate for both methods that can be evaluated in linear memory without transport plan construction, thus providing a computable stopping rule. On the DOTmark benchmark, combining momentum with the cooler kernel produces substantially smaller optimality gaps than annealed Sinkhorn under the same schedule. For pixel-level color transfer between 1024×10241024\times1024 images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9×\times speed up, reaching a relative duality gap of 1.59%1.59\% in 24 minutes. We further demonstrate a color transfer with 4238×23654238\times2365 images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of 2.41%2.41\% and 2.80%2.80\% within 35 hours in each direction on a single NVIDIA L40S GPU.