论文标题
半屏亚最佳运输问题的区块坐标弗兰克 - 沃尔夫算法和收敛分析
Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem
论文作者
论文摘要
最佳运输（OT）问题已被广泛用于机器学习。计算OT问题是必要的，以求解具有严格的质量保存约束的线性编程。这些限制阻止其应用于大规模问题。为了解决这个问题，放松这种约束使我们能够使用更快的算法提出放松的方法。这种方法证明了其对应用的有效性。但是，它仍然很慢。作为优越的替代方法，我们为凸半释放的OT提出了一种快速座位的Frank-Wolfe（BCFW）算法。具体而言，我们证明了它们的上限最差的融合迭代，以及线性二元间隔和拉格朗日二元性差距之间的等效性。此外，我们开发了拟议的BCFW的两个快速变体。数值实验表明，我们提出的算法对色彩传递和超过最新算法有效。该报告介绍了Arxiv的简短版本：2103.05857。
The optimal transport (OT) problem has been used widely for machine learning. It is necessary for computation of an OT problem to solve linear programming with tight mass-conservation constraints. These constraints prevent its application to large-scale problems. To address this issue, loosening such constraints enables us to propose the relaxed-OT method using a faster algorithm. This approach has demonstrated its effectiveness for applications. However, it remains slow. As a superior alternative, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm for a convex semi-relaxed OT. Specifically, we prove their upper bounds of the worst convergence iterations, and equivalence between the linearization duality gap and the Lagrangian duality gap. Additionally, we develop two fast variants of the proposed BCFW. Numerical experiments have demonstrated that our proposed algorithms are effective for color transfer and surpass state-of-the-art algorithms. This report presents a short version of arXiv:2103.05857.
