# Accelerated Sinkhorn Algorithms for Partial Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 23 Jan 2026.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [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)
- [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Scaling Algorithms for Unbalanced Transport Problems](https://mlsanity.com/paper/1607.05816/) (2016)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Unbalanced Optimal Transport: A Unified Framework for Object Detection](https://mlsanity.com/paper/2307.02402/) (2023)
- [P2OT: Progressive Partial Optimal Transport for Deep Imbalanced Clustering](https://mlsanity.com/paper/2401.09266/) (2024)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions](https://mlsanity.com/paper/2405.03664/) (2024)
- [Partial Wasserstein Adversarial Network for Non-rigid Point Set Registration](https://mlsanity.com/paper/2203.02227/) (2022)
- [Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm](https://mlsanity.com/paper/2210.16645/) (2022)
- [SP2OT: Semantic-Regularized Progressive Partial Optimal Transport for Imbalanced Clustering](https://mlsanity.com/paper/2404.03446/) (2024)
- [An Optimal Transport-Based Generative Model for Bayesian Posterior Sampling](https://mlsanity.com/paper/2504.08214/) (2025)
- [Control, Optimal Transport and Neural Differential Equations in Supervised Learning](https://mlsanity.com/paper/2503.15105/) (2025)

## Abstract (arXiv)

Partial Optimal Transport (POT) addresses the problem of transporting only a fraction of the total mass between two distributions, making it suitable when marginals have unequal size or contain outliers. While Sinkhorn-based methods are widely used, their complexity bounds for POT remain suboptimal and can limit scalability. We introduce Accelerated Sinkhorn for POT (ASPOT), which integrates alternating minimization with Nesterov-style acceleration in the POT setting, yielding a complexity of O(n7/3varepsilon-5/3). We also show that an informed choice of the entropic parameter γ improves rates for the classical Sinkhorn method. Experiments on real-world applications validate our theories and demonstrate the favorable performance of our proposed methods.