Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.17196 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908935701659648 |
|---|---|
| author | Truong, Nghia Thu Pham, Qui Phu Nguyen, Quang Luong, Dung Tran, Mai |
| author_facet | Truong, Nghia Thu Pham, Qui Phu Nguyen, Quang Luong, Dung Tran, Mai |
| contents | 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 $\mathcal{O}(n^{7/3}\varepsilon^{-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17196 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Accelerated Sinkhorn Algorithms for Partial Optimal Transport Truong, Nghia Thu Pham, Qui Phu Nguyen, Quang Luong, Dung Tran, Mai Machine Learning 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 $\mathcal{O}(n^{7/3}\varepsilon^{-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. |
| title | Accelerated Sinkhorn Algorithms for Partial Optimal Transport |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2601.17196 |