# On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 42 references that are in the map.
- First posted on arXiv 21 Dec 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015)
- [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)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Scalable Unbalanced Optimal Transport using Generative Adversarial Networks](https://mlsanity.com/paper/1810.11447/) (2018)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [Scaling Algorithms for Unbalanced Transport Problems](https://mlsanity.com/paper/1607.05816/) (2016)
- [A Smoothed Dual Approach for Variational Wasserstein Problems](https://mlsanity.com/paper/1503.02533/) (2015)
- [Fast Optimal Transport Averaging of Neuroimaging Data](https://mlsanity.com/paper/1503.08596/) (2015)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Improved Complexity Bounds in Wasserstein Barycenter Problem](https://mlsanity.com/paper/2010.04677/) (2020)
- [Robust Estimation under the Wasserstein Distance](https://mlsanity.com/paper/2302.01237/) (2023)
- [Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization](https://mlsanity.com/paper/2101.00143/) (2021)
- [Stochastic Approximation for Nonlinear Discrete Stochastic Control: Finite-Sample Bounds](https://mlsanity.com/paper/2304.11854/) (2023)

## Built on by (most cited first, 7 of 7)

- [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024)
- [UniPROT: Uniform Prototype Selection via Partial Optimal Transport with Submodular Guarantees](https://mlsanity.com/paper/2604.10952/) (2026)
- [Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin](https://mlsanity.com/paper/2501.18143/) (2025)
- [Sparse Partial Optimal Transport via Quadratic Regularization](https://mlsanity.com/paper/2508.08476/) (2025)
- [HOT-POT: Optimal Transport for Sparse Stereo Matching](https://mlsanity.com/paper/2601.12423/) (2026)
- [Accelerated Sinkhorn Algorithms for Partial Optimal Transport](https://mlsanity.com/paper/2601.17196/) (2026)
- [Accelerated Algorithm for Sparse Regularized Partial Optimal Transport](https://mlsanity.com/paper/2609.40075/) (2026)

## Abstract (arXiv)

This paper studies the Partial Optimal Transport (POT) problem between two unbalanced measures with at most n supports and its applications in various AI tasks such as color transfer or domain adaptation. There is hence the need for fast approximations of POT with increasingly large problem sizes in arising applications. We first theoretically and experimentally investigate the infeasibility of the state-of-the-art Sinkhorn algorithm for POT due to its incompatible rounding procedure, which consequently degrades its qualitative performance in real world applications like point-cloud registration. To this end, we propose a novel rounding algorithm for POT, and then provide a feasible Sinkhorn procedure with a revised computation complexity of widetilde O(n2/varepsilon4). Our rounding algorithm also permits the development of two first-order methods to approximate the POT problem. The first algorithm, Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD), finds an varepsilon-approximate solution to the POT problem in widetilde O(n2.5/varepsilon), which is better in varepsilon than revised Sinkhorn. The second method, Dual Extrapolation, achieves the computation complexity of widetilde O(n2/varepsilon), thereby being the best in the literature. We further demonstrate the flexibility of POT compared to standard OT as well as the practicality of our algorithms on real applications where two marginal distributions are unbalanced.