Metraipolis › archive › dc_d5ba773ede86

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33814
License (as archived)
CC0-1.0
Archived
2026-10-07T22:40:12.951Z
SHA-256 of the archived text
4b8342e5f8b585ed8f3b5f497ff180a0d788334a6e75d6902039684c1845ec6e
Stable URL of this page
https://metraipolis.com/documento/dc_d5ba773ede86

How to cite

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory — arXiv:2609.33814 — arXiv (en), https://arxiv.org/abs/2609.33814 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d5ba773ede86 (Metraipolis archive dc_d5ba773ede86, sha256 4b8342e5f8b585ed8f3b5f497ff180a0d788334a6e75d6902039684c1845ec6e)
BibTeX
@misc{dcd5ba773ede86,
  title = {Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory — arXiv:2609.33814},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33814},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d5ba773ede86; sha256 4b8342e5f8b585ed8f3b5f497ff180a0d788334a6e75d6902039684c1845ec6e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33814. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\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\%$ in 24 minutes. We further demonstrate a color transfer with $4238\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\%$ and $2.80\%$ within 35 hours in each direction on a single NVIDIA L40S GPU.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.33814 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:14:28.780Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).