Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem

Abstract

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.

arXiv commentIEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP2022). arXiv admin note: substantial text overlap with arXiv:2103.05857

References in corpus (5)

• Learning with a Wasserstein Loss
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs
• Generalized conditional gradient: analysis of convergence and applications
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport

Cited by in corpus (2)

• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space
• Anchor Space Optimal Transport as a Fast Solution to Multiple Optimal Transport Problems