We introduce in this paper a novel strategy for efficiently approximate the Sinkhorn distance between two discrete measures. After identifying neglectible components of the dual solution of the regularized Sinkhorn problem, we propose to screen those components by directly setting them at that value before entering the Sinkhorn problem. This allows us to solve a smaller Sinkhorn problem while ensuring approximation with provable guarantees. More formally, the approach is based on a reformulation of dual of Sinkhorn divergence problem and on the KKT optimality conditions of this problem, which enable identification of dual components to be screened. This new analysis leads to the Screenkhorn algorithm. We illustrate the efficiency of Screenkhorn on complex tasks such as dimensionality reduction or domain adaptation involving regularized optimal transport.

本研究提出了一种新颖的策略以有效地近似两个离散度量之间的 Sinkhorn 距离。通过直接将可忽略的双重解的组件设置为该值，我们建议通过筛选这些组件来进入 Sinkhorn 问题。这基于 Sinkhorn 分歧问题的新增双重的新公式和该问题的 KKT 最优性条件，其可从该问题中识别可筛选的双重组件，从而确保了可证明的近似。在包括规则化最优输送的复杂任务中，我们展示了 Screenkhorn 的效率，例如维数约简和领域适应。

基于放松约束的最优输运筛选Sinkhorn算法