Open AccessEfficient Optimal Transport Algorithm by Accelerated Gradient Descent
Author(s) -
Dongsheng An,
Na Lei,
Xianfeng Gu
Publication year - 2022
Publication title -
proceedings of the ... aaai conference on artificial intelligence
Language(s) - Uncategorized
Resource type - Journals
eISSN - 2374-3468
pISSN - 2159-5399
DOI - 10.1609/aaai.v36i9.21251
Subject(s) - algorithm , computer science , smoothing , convergence (economics) , gradient descent , mathematical optimization , function (biology) , entropy (arrow of time) , convex function , thresholding , mathematics , regular polygon , artificial intelligence , artificial neural network , image (mathematics) , physics , quantum mechanics , evolutionary biology , economics , computer vision , biology , economic growth , geometry
Optimal transport (OT) plays an essential role in various areas like machine learning and deep learning. However, computing discrete OT for large scale problems with adequate accuracy and efficiency is highly challenging. Recently, methods based on the Sinkhorn algorithm add an entropy regularizer to the prime problem and obtain a trade off between efficiency and accuracy. In this paper, we propose a novel algorithm based on Nesterov's smoothing technique to further improve the efficiency and accuracy in computing OT. Basically, the non-smooth c-transform of the Kantorovich potential is approximated by the smooth Log-Sum-Exp function, which smooths the original non-smooth Kantorovich dual functional. The smooth Kantorovich functional can be efficiently optimized by a fast proximal gradient method, the fast iterative shrinkage thresholding algorithm (FISTA). Theoretically, the computational complexity of the proposed method is given by O ( n 5 2log n∕ ϵ ) , which is lower than current estimation of the Sinkhorn algorithm. Experimentally, compared with the Sinkhorn algorithm, our results demonstrate that the proposed method achieves faster convergence and better accuracy with the same parameter.