Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem
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.