提出加速算法ASPOT，显著提升部分最优传输计算效率
Accelerated Sinkhorn Algorithms for Partial Optimal Transport
- 结合交替最小化与Nesterov加速，改进部分最优传输求解
- 理论复杂度降至O(n^{7/3}ε^{-5/3})，优于传统方法
- 适合大规模分布匹配、含异常值场景的高效计算
部分最优传输（POT）解决两分布间仅搬运部分质量的问题，适用于边际大小不等或含异常值的情形。尽管基于Sinkhorn的方法广泛使用，其在POT下的复杂度仍不理想，制约可扩展性。本文提出面向POT的加速Sinkhorn算法（ASPOT），在POT设定中融合交替最小化与Nesterov风格加速，将复杂度优化至$/mathcal{O}(n^{7/3}\varepsilon^{-5/3})$。同时，我们证明了熵参数$γ$的合理选择能提升经典Sinkhorn方法的收敛速率。真实世界应用实验验证了理论分析，并展示了所提方法的优越性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。