CS Paper Radar

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren, Reuben Dorent

cs.LG ·submitted 2026-08-28 12:24 UTC · v1
theorycode/data

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Accelerated Algorithm for Sparse Regularized Partial Optimal Transport

cs.LG ·2026-09-30 ·Khoa Nguyen, Dung T. Nguyen, Thong Huynh, Hoang-Hiep Nguyen-Mau, Anh Nguyen +2 more
similarity 0.74
Abstract · 39 pages, 13 figures

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.

0.10

EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset

cs.LG stat.ML ·2026-08-17 ·Haoyun Yin, Chuanhui Liu, Xiao Wang
similarity 0.71
Abstract

Coresets distill large datasets into small, representative subsets for efficient downstream learning. Yet Optimal Transport (OT)-based selection typically requires intensive computation of transport plans, limiting scalability. We introduce a scalable Sinkhorn coreset method that permits closed-form updates of the entropically regularized OT coupling by allowing non-uniform coreset weights. This produces centroids that generalize k-means via soft assignments. We establish asymptotic consistency of the selected measure and Lipschitz stability to data perturbations, providing accuracy and robustness guarantees. Across synthetic and real-world benchmarks, the proposed method achieves competitive or improved approximation quality while substantially reducing runtime compared to Wasserstein- and standard Sinkhorn-based coreset selection, especially at large scale.

0.22

Learning Optimal Transport Plans Via Autoregressive Token Regression

cs.LG cs.AI ·2026-11-17 ·Ivan Jaen Marquez, Sotirios Panagiotis Chytas, Vikas Singh
similarity 0.65
Abstract

Optimal Transport (OT) provides a principled framework for finding the minimum cost coupling between probability distributions. Classical solvers remain the gold standard for this task. At the same time, OT is an ideal testbed for studying whether learning-based amortized models can internalize the structure of OT type problems. Here, ground-truth solutions are available and marginal constraints are explicitly defined. Also, exact discrete solutions have well-characterized sparsity. We describe ToR-OT, a transformer-based model that learns to predict discrete OT plans through autoregressive token regression. We reframe OT into a structured sequence generation task. ToR-OT decodes sparse transport plans as sequences instead of solving an optimization task at test time. We focus on three properties: (a) Zero-shot generalization: pretraining on a large synthetic corpus of OT instances allows a single model to generalize to unseen distribution pairs and heterogeneous cost metrics without retraining, (b) Sparse primal decoding: by exploiting the inherent sparsity in exact discrete OT solutions, the decoder predicts only nonzero entries (avoids dense coupling outputs), (c) Amortized inference: on low-dimensional discrete problems, ToR-OT gives accurate approximate plans and compares favorably with per-instance neural OT baselines. Overall, ToR-OT is not yet a replacement for classical solvers, but a step toward understanding how autoregressive transformers can learn structure of constrained optimization problems like OT.

0.14

Statistical Rates for Entropic Optimal Transport in the Discrete to SubGaussian Regime

cs.LG math.ST ·2026-09-22 ·Tomas Gonzalez, Gonzalo Mena
theory similarity 0.65
Abstract

We study statistical rates in entropic optimal transport in the semi-discrete regime where one measure has finite support and the other is subGaussian. Our main result establishes parametric convergence rates for the empirical dual potentials to their population counterparts, with no dimension dependence in the leading term. Our result relies on tailored strong concavity analysis of the semi-dual objective, coupled with specialized bounds for the semi-discrete potentials. As a consequence, we obtain fast rates for downstream quantities derived from the optimal coupling. Chiefly, the empirical barycentric projection achieves a squared-error rate $n^{-1}$, matching the fully compact case and improving over the less favorable $n^{-1/2}$ rate known for fully subGaussian settings. Altogether, these results may indicate a lower complexity adaptation phenomenon whereby the statistical complexity of the barycentric projection is governed by the discrete measure. As an application, we analyze Sinkhorn-EM, an EM-type algorithm in which the E-step is replaced by an entropic optimal transport problem. In a well-specified and balanced two-component Gaussian mixture model, we prove $\sqrt{n}$-consistency of the empirical iterates to their population counterparts for any fixed number of iterations, matching classical EM rates up to a $\sqrt{\log n}$ factor. Simulations support the theory.

0.12

One-Step Generative Modeling via Unbalanced Optimal Transport

cs.IT cs.LG ·2026-09-26 ·Yirong Shen, Mengfei Xia, Junpeng Jing, Lu Gan, Cong Ling
similarity 0.64
Abstract

Drifting models enable one-step generation by amortizing distribution transport into training, but this efficiency places greater demands on the transport field estimated at each update. In large-scale training, the field is computed from finite mini-batches of generated and real samples, which provide only imperfect approximations to the underlying distributions. Balanced optimal transport enforces exact mass matching within every mini-batch, making the estimated field sensitive to the particular composition of the real-data batch. We find that generated and real samples should be treated asymmetrically: letting the mass assigned to real samples adapt while keeping every generated sample fully transported improves generation across six feature-space metrics in controlled ablations, and is more robust to the relaxation strength than relaxing both marginals simultaneously, which falls below balanced transport under stronger relaxation. Motivated by this observation, we propose Unbalanced Optimal Transport Gradient Flow (UOT-GF), which keeps the generated-sample marginal fixed and relaxes only the real-data marginal. Under identical settings at DiT-B/2 on ImageNet-256, UOT-GF improves Fréchet Inception Distance (FID) from 1.53 to 1.46 over the balanced W-Flow baseline; scaling the same recipe yields 1.34 and 1.22 FID at L/2 and XL/2, the best FID among the one-step models we compare. We further derive the induced UOT transport force, establish a kinetic Vlasov--Fokker--Planck formulation whose overdamped zero-temperature limit recovers the drifting dynamics, and characterize non-target stationary states together with sufficient conditions for convergence.

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.64
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.50

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

AdjointFlow: Accelerating Scientific Inverse Problems with Physics-Based Transport

cs.LG ·2026-11-10 ·Ethan Hanold, Nicholas M. Boffi, Qin Li, Leonardo Zepeda-Núñez
similarity 0.63
Abstract · 51 pages, 17 figures, including appendices

Inverse problems are ubiquitous across scientific applications ranging from seismic imaging to astrophysics to nondestructive testing, yet classical solvers often struggle with nonconvexity and repeated evaluations of expensive physical models. Diffusion models can amortize this computation offline, but largely data-driven conditional models underutilize known physics and suffer from ill-conditioned transport maps when the target distribution is concentrated. Plug-and-play (PnP) methods explicitly leverage the physical model to guide a learned prior, improving data consistency but reintroducing costly iterative computations. We instead propose AdjointFlow, a framework built on stochastic interpolants that injects the known physics into the generative transport itself. We design a data-dependent, adjoint-based initialization to reduce transport distance to the target, modify the transport velocity to remain regular as the endpoint distributions concentrate, and parameterize the network to build the initialization directly into the learned velocity. Together, these enable accurate reconstruction at substantially lower cost than generative models starting from Gaussian noise. Experiments on inverse scattering, seismic imaging, and black hole imaging show that AdjointFlow consistently produces more accurate reconstructions than conditional diffusion models while being up to five orders of magnitude faster at inference than PnP methods. Optional inference-time refinement that queries the physical model can further improve data consistency, matching or exceeding the accuracy of PnP methods without retraining.

0.22