TY - GEN
T1 - BLOCK-COORDINATE FRANK-WOLFE ALGORITHM AND CONVERGENCE ANALYSIS FOR SEMI-RELAXED OPTIMAL TRANSPORT PROBLEM
AU - Fukunaga, Takumi
AU - Kasai, Hiroyuki
N1 - Funding Information:
∗H. Kasai was partially supported by JSPS KAKENHI Grant Numbers JP16K00031 and JP17H01732, and by Support Center for Advanced Telecomm. Technology Research (SCAT).
Publisher Copyright:
© 2022 IEEE
PY - 2022
Y1 - 2022
N2 - 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 [1]. The source code is available at https://github.com/hiroyuki-kasai/srot.
AB - 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 [1]. The source code is available at https://github.com/hiroyuki-kasai/srot.
KW - Block-coordinate Frank-Wolfe algorithm
KW - color transfer
KW - optimal transport
KW - semi-relaxed optimal transport
UR - http://www.scopus.com/inward/record.url?scp=85131262858&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85131262858&partnerID=8YFLogxK
U2 - 10.1109/ICASSP43922.2022.9746032
DO - 10.1109/ICASSP43922.2022.9746032
M3 - Conference contribution
AN - SCOPUS:85131262858
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 5433
EP - 5437
BT - 2022 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2022 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 47th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2022
Y2 - 23 May 2022 through 27 May 2022
ER -