CSG: Complementary Slackness Guidance for Solving Optimal Transport Problem

Optimal Transport (OT) has become a cornerstone mathematical tool in machine learning for measuring discrepancies between probability distributions. Directly solving the optimal transport problem can be relatively difficult with high complexity. Conventional solvers often employ relaxation approaches (i.e., entropic regularization) to achieve estimated matching results. However, these methods frequently yield dense and ambiguous outputs and thereby degrading the model performance. To address this issue, we propose the Complementary Slackness Guidance (CSG) approach to tackle the OT problem. That is, CSG introduces a novel Conditional Regularization Mask (CRM) that incorporates multiplier information by enlarging the irrelevant cost distances, thereby enabling more precise solutions. Specifically, CSG involves exploration and utilization stages to further estimate and leverage the Lagrange multipliers for the whole computation. We conduct several numerical experiments to demonstrate the effectiveness of our proposed CSG methods with the CRM term in addressing OT problems.