Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem
This work addresses the slow computation of optimal transport for large-scale machine learning problems, representing an incremental improvement over existing relaxed methods.
The authors tackled the computational inefficiency of the relaxed optimal transport method by proposing a fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport, which demonstrated effectiveness in color transfer and surpassed state-of-the-art algorithms.
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.