Safe Screening for Unbalanced Optimal Transport

Optimal transport (OT), as a metric, has gained significant attention in the field of machine learning in recent years due to its remarkable ability to capture geometric relationships between data distributions. It has demonstrated impressive achievements in many fields [16, 3, 13, 31]. To overcome the limitation of OT in handling data with unequal quantities, researchers introduced unbalanced optimal transport (UOT) [8] by relaxing the constraints using penalty functions. UOT has been found extensive applications in computational biology [40], machine learning [25], and deep learning domains [51]. However, compared to traditional metrics, the computational burden associated with OT, including UOT, has impeded their widespread adoption on large-scale problems. The state-of-the-art linear programming algorithms suffer from cubic computational complexity and are challenging to parallelize on GPUs [46].