Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory
Abstract
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×1024 images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9× speed up, reaching a relative duality gap of 1.59% in 24 minutes. We further demonstrate a color transfer with 4238×2365 images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of 2.41% and 2.80% within 35 hours in each direction on a single NVIDIA L40S GPU.
Related
- Accelerating Sinkhorn for Entropy-Regularized Optimal Transport
- Exponential convergence of Sinkhorn algorithm for entropy martingale optimal transport
- Beyond Empirical Support: Structured Outlier Generation via Sinkhorn Optimal Transport
- Forward Tangent-Centered Sinkhorn DRO: Exact Nominal Recovery from Optimal Transport to KL
- Relevance Propagation as Entropic Optimal Transport on Filippov Neural Networks: Sinkhorn Propagation and Region Relevance in Image Classifiers
BibTeX
@misc{chin2026annealed,
title = {{Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory}},
author = {Samuel J. K. Chin and Maximilian Schiffer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33814},
eprint = {2609.33814},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33814},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory
AU - Samuel J. K. Chin
AU - Maximilian Schiffer
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33814
UR - https://arxiv.org/abs/2609.33814
AB - 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×1024 images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9× speed up, reaching a relative duality gap of 1.59% in 24 minutes. We further demonstrate a color transfer with 4238×2365 images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of 2.41% and 2.80% within 35 hours in each direction on a single NVIDIA L40S GPU.
ER -