CS Paper Radar

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

Samuel J. K. Chin, Maximilian Schiffer

cs.LG math.OC ·submitted 2026-09-27 18:09 UTC · v1
benchmark

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\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.

Comment
38 pages, 11 figures

Closest papers

Nearest neighbours by meaning across the whole index.

GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport

cs.LG math.OC ·2026-10-03 ·Yifan Xu, Shiqian Ma
benchmark similarity 0.64
Abstract · 44 pages, 7 figures, 3 tables. Submitted to Mathematical Programming Computation

We present GPU-accelerated Bregman Douglas--Rachford splitting algorithm (BDRS) for discrete optimal transport problem in three input formats: an explicit cost matrix, a point cloud with a ground cost between them, and a separable cost on a regular grid. For each input format, we propose hardware-aware designs of mathematically equivalent representations for the BDRS iterations to enhance numerical stability and empirical runtime. We benchmark the three proposed implementations against eight GPU baseline solvers from the literature on the same device. We demonstrate that our implementations of BDRS achieve state-of-the-art performance on their respective input formats. To the best of our knowledge, this is the first cross-solver study of GPU DOT solvers with a unified measure of optimality.

0.25

Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions

cs.LG ·2026-09-11 ·Wenzhou Xia, Qiaoqiao Ding, Jingwei Liang, Xiaoqun Zhang
theory similarity 0.59
Abstract

Optimal transport (OT) compares distributions and aligns datasets in machine learning, yet unregularized discrete OT requires a linear program with quadratically many transport variables. We propose HELLO, a hierarchical solver that casts large-scale discrete OT as edge localization and uses dual potentials to guide both coarse-to-fine initialization and within-level refinement. Initialization propagates coarse dual potentials across a recursive subsampling hierarchy to assign candidate edges. Refinement then iteratively inserts the largest dual violators in each row and column until the relative KKT residual meets a prescribed tolerance, while budgeted pruning ensures linear memory complexity. For exact-arithmetic refinement, we prove finite termination at a global optimum under a symbolic lexicographic rule. At the million-point scale, HELLO attains lower transport objectives with order-of-magnitude runtime improvements over strong baselines across feature dimensions from single digits to thousands. It further scales to 1.28 million samples per marginal in 8192 dimensions on a single H100, using 41.6 GiB peak GPU memory while satisfying a full relative KKT residual below $10^{-6}$. Beyond standard discrete OT, the framework supports general pairwise costs and serves as a scalable balanced-OT oracle for semi-discrete OT, Gromov--Wasserstein, unbalanced OT, and OT-based Flow Matching.

0.49

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

cs.LG ·2026-08-28 ·Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren, Reuben Dorent
theorycode/data similarity 0.58
Abstract

Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with $N$ points, each iteration requires $O(N^2)$ operations, which restricts its use on large-scale datasets (e.g. $N\geq10^4$). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with $L$ slices, each resulting sparse Sinkhorn iteration costs $O(LN)$; and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.

0.19

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

cs.LG math.OCquant-ph ·2026-09-03 ·A. Afham
similarity 0.56
Abstract · 33 Pages, 3 figures. Comments welcome!

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, $(1 - κ^{-3/2})$, where $κ$ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee ($κ^{3/2}$ versus $κ^{5/2}$ iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval $[α, β]$ is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set $\{S : αI \leq S \leq βI\}$ -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

0.20

Faster Algorithms for Multimarginal Optimal Transport

cs.DS quant-phmath.OC ·2026-08-10 ·Brandon Augustino, Yue Sun, Atithi Acharya, Shouvanik Chakrabarti, Junhyung Lyle Kim +2 more
theory similarity 0.55
Abstract

We study constructive discrete multimarginal optimal transport (MOT) among $m$ distributions on $n$ points, where the cost tensor $C$ has $N=n^m$ entries. For additive accuracy $\varepsilon$, let $κ=\max\{1,(\max C-\min C)/\varepsilon\}$. Classically, we give two algorithms that return exactly feasible additive-$\varepsilon$ couplings. A deterministic box--simplex method with rounding runs in $O(m^2Nκ\log N)=\widetilde O(m^3Nκ)$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\widetilde O(m^2Nκ)$. At fixed $κ$, both match the $Ω(N)$ cost of writing a dense coupling, up to factors in $m$ and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-$\varepsilon$ coupling as a classical list of $\widetilde O(m^2nκ^2)$ atoms, using $\widetilde O(m^4\sqrt{Nn}\,κ^3)$ coherent cost queries without materializing the tensor. Finally, for fixed $m$ and constant normalized accuracy, we prove sparse-output lower bounds of $\widetildeΩ(N)$ randomized classical queries, even with unrestricted output size, and $\widetildeΩ(\sqrt{Nn})$ quantum queries for outputs with at most $n\operatorname{polylog}(n)$ atoms. Hence, for fixed $m$ and normalized accuracy between $(\log n)^{-O(1)}$ and a sufficiently small constant, explicit sparse MOT construction has query complexity $\widetildeΘ(N)$ classically and $\widetildeΘ(\sqrt{Nn})$ quantumly.

0.04

Support Topology and Gradient Mixing in Sinkhorn Layers

cs.AI cs.LG ·2026-09-07 ·Dylan Forde
similarity 0.55
Abstract

Sparse Sinkhorn layers use a fixed support graph to restrict transport between tokens. How does this graph control gradient propagation through the scaling iterations. We develop a fixed-support calculus showing that each row-column cycle induces a row-stochastic operator on column-potential perturbations modulo constants. Its transpose propagates zero-mass reverse-mode cotangents. The finite-cycle operator uses two distinct half-step transport plans; at a balanced fixed point it reduces to a two-step walk determined by a single plan. We derive the accompanying score and marginal source terms and use Dobrushin contraction and minorization to bound homogeneous and source-driven tail cotangents. Our main result characterizes when support and marginals guarantee one-step contraction uniformly over finite scores: every feasible face of the transportation polytope must have pairwise two-hop column overlap. Otherwise, suitable score directions make the contraction coefficient arbitrarily close to one. We extend this analysis to ordered support schedules and derive certificates for partition heat-bath layers, coordinate sweeps, forced shared mass, and register-augmented supports. These results provide mathematical criteria for support design in differentiable transport layers, with guarantees restricted to the fixed-support quotient-gradient component.

0.25

Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption

cs.LG math.OC ·2026-09-06 ·Daniel Cortild, Mathias Staudigl, Juan Peypouquet, Coralia Cartis
similarity 0.54
Abstract

We investigate stochastic simple bilevel optimization with smooth and possibly nonconvex upper- and lower-level objectives. Existing stochastic extensions of dynamic barrier gradient descent (DBGD) either obtain fast convergence under an unverifiable trajectory-dependent ``rare-visit'' assumption, or remove this assumption at a substantially higher oracle cost. We show that a simple denominator-only regularization of the DBGD multiplier eliminates the need for such an assumption while preserving fast convergence rates. Specifically, our method achieves $(\varepsilon, \varepsilon)$-stationarity in $O(\varepsilon^{-2})$ iterations using $O(\varepsilon^{-4})$ upper-level and $O(\varepsilon^{-7})$ lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.

0.34

FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport

cs.AI astro-ph.IMmath.NA ·2026-10-01 ·Felix X. -F. Ye, Yu Chin Fabian Lim, Naigang Wang, Davis Wertheimer
code/data similarity 0.54
Abstract

Streaming GPU solvers for entropic optimal transport (EOT), such as FlashSinkhorn, avoid storing the dense kernel but still evaluate all $n\times m$ point pairs in every Sinkhorn iteration. We present \textbf{FlashSinkhorn~2} (FS2), a solver for squared-Euclidean cost on low-dimensional point clouds that solves large discrete EOT problems to a prescribed marginal residual on a single GPU by coupling two stages. A coarse stage solves on cell centroids, lifts the potentials to every point and, when a sampled marginal check rejects the lift, continues on the centroids, replacing most point-level updates. A block-sparse fine stage then removes the centroid error that coarse updates cannot. Its Morton-ordered blocks support screening and fused tensor-core execution, and a threshold set by the block masses bounds each omitted tile's contribution to every row and column. On synthetic benchmarks, FS2 reaches the target residual on all 32 problems and GeomLoss multiscale on 10. On one A100, FS2 solves discrete EOT between two $1.34\times10^8$-particle measures from a cosmological $N$-body simulation, at an entropic blur equal to the mean interparticle distance, to an all-particle marginal residual below 0.01 in under 2.5 hours. To our knowledge, it is the largest discrete EOT problem solved to this accuracy within hours. For reproducibility, we release an open-source implementation at https://github.com/ot-triton-lab/flash-sinkhorn

0.36