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

arXiv: https://arxiv.org/abs/2609.33814 · HTML: https://mlsanity.com/paper/2609.33814/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Builds on (most cited first, 19 of 19)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1711.01851/) (2017)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementation](https://mlsanity.com/paper/2110.11738/) (2021)
- [Bregman Proximal Point Algorithm Revisited: A New Inexact Version and its Inertial Variant](https://mlsanity.com/paper/2105.10370/) (2021)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [A Truncated Newton Method for Optimal Transport](https://mlsanity.com/paper/2504.02067/) (2025)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport](https://mlsanity.com/paper/2407.19689/) (2024)
- [Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs](https://mlsanity.com/paper/2305.18483/) (2023)
- [Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings](https://mlsanity.com/paper/2311.02172/) (2023)
- [Bregman Douglas-Rachford Splitting Method](https://mlsanity.com/paper/2509.08739/) (2025)
- [Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space](https://mlsanity.com/paper/2511.11359/) (2025)
- [Inexact Bregman Sparse Newton Method for Efficient Optimal Transport](https://mlsanity.com/paper/2603.07156/) (2026)

## Abstract (arXiv)

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.