Accelerated Sinkhorn Algorithms for Partial Optimal Transport
This addresses scalability issues in POT for applications with unequal distribution sizes or outliers, representing an incremental improvement over existing methods.
The paper tackles the computational complexity limitations of Sinkhorn-based methods for Partial Optimal Transport (POT), introducing ASPOT with alternating minimization and Nesterov-style acceleration to achieve a complexity of O(n^{7/3}ε^{-5/3}) and showing improved rates for classical Sinkhorn through better entropic parameter selection.
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.