mlsanityData to 14 Oct 2026

Accelerated Sinkhorn Algorithms for Partial Optimal Transport

arXiv 2601.17196 ↗First posted 23 Jan 2026cs.LGcited by 0

Not on the map. Why?

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.

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

23 of 45 references.

References · 23

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  2. 2017Learning Generative Models with Sinkhorn Divergencescited by 314
  3. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 223
  4. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 112
  5. 2020Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptationcited by 87
  6. 2019Statistical bounds for entropic optimal transport: sample complexity and the central limit theoremcited by 85
  7. 2017Smooth and Sparse Optimal Transportcited by 83
  8. 2016Scaling Algorithms for Unbalanced Transport Problemscited by 36
  9. 2019On the Efficiency of Entropic Regularized Algorithms for Optimal Transportcited by 35
  10. 2021On Robust Optimal Transport: Computational Complexity and Barycenter Computationcited by 27
  11. 2023Scalable Optimal Transport Methods in Machine Learning: A Contemporary Surveycited by 27
  12. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
11 more
  1. 2023Unbalanced Optimal Transport: A Unified Framework for Object Detectioncited by 15
  2. 2024P2OT: Progressive Partial Optimal Transport for Deep Imbalanced Clusteringcited by 13
  3. 2021On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexitycited by 8
  4. 2023Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradientscited by 7
  5. 2023On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methodscited by 7
  6. 2024A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributionscited by 7
  7. 2022Partial Wasserstein Adversarial Network for Non-rigid Point Set Registrationcited by 5
  8. 2022Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithmcited by 3
  9. 2024SP2OT: Semantic-Regularized Progressive Partial Optimal Transport for Imbalanced Clusteringcited by 2
  10. 2025An Optimal Transport-Based Generative Model for Bayesian Posterior Samplingcited by 2
  11. 2025Control, Optimal Transport and Neural Differential Equations in Supervised Learningcited by 1

Built on by

Not cited yet.