[2S6-IS-3d] Machine learning

[2S6-IS-3d-03] Development and analysis of optimization algorithm for relaxed optimal transport

〇Takumi Fukunaga¹, Hiroyuki Kasai¹ (1. Waseda University)

Regular

Keywords:optimal transport, relaxed optimal transport, optimization algorithm

Optimal transport has attracted wide interest because it can express Wasserstein distance. Although it is defined as linear programming problem with tight constraints, it is known that linear programming problem is difficult to solve efficiently. To facilitate this problem, a relaxed optimal transport loosing the constraints has been proposed. It develops the fast methods and, moreover, reduces the performance degradation of some applications (color transfer, etc) which OT does not work well on. However, it remains slow. To address this issue, this paper proposes the fast optimization method using block--coordinate Frank--Wolfe (BCFW) algorithm for semi-relaxed optimal transport. Furthermore, it also develops three fast variants of BCFW with away-steps, pairwise-steps, and gap-sampling. Numerical evaluations show that our proposed fast variants converge more fast than original BCFW.