Improved Rate of First Order Algorithms for Entropic Optimal Transport

Yiling Luo, Yiling Xie, Xiaoming Huo
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:2723-2750, 2023.

Abstract

This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from $\widetilde{\mathcal{O}}({n^{2.5}}/{\epsilon})$ to $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$, where $n$ is the problem size and $\epsilon$ is the accuracy level. In particular, we propose an accelerated primal-dual stochastic mirror descent algorithm with variance reduction. Such special design helps us improve the rate compared to other accelerated primal-dual algorithms. We further propose a batch version of our stochastic algorithm, which improves the computational performance through parallel computing. To compare, we prove that the computational complexity of the Stochastic Sinkhorn algorithm is $\widetilde{\mathcal{O}}({n^2}/{\epsilon^2})$, which is slower than our accelerated primal-dual stochastic mirror algorithm. Experiments are done using synthetic and real data, and the results match our theoretical rates. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$ for solving OT.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-luo23a, title = {Improved Rate of First Order Algorithms for Entropic Optimal Transport}, author = {Luo, Yiling and Xie, Yiling and Huo, Xiaoming}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {2723--2750}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/luo23a/luo23a.pdf}, url = {https://proceedings.mlr.press/v206/luo23a.html}, abstract = {This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from $\widetilde{\mathcal{O}}({n^{2.5}}/{\epsilon})$ to $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$, where $n$ is the problem size and $\epsilon$ is the accuracy level. In particular, we propose an accelerated primal-dual stochastic mirror descent algorithm with variance reduction. Such special design helps us improve the rate compared to other accelerated primal-dual algorithms. We further propose a batch version of our stochastic algorithm, which improves the computational performance through parallel computing. To compare, we prove that the computational complexity of the Stochastic Sinkhorn algorithm is $\widetilde{\mathcal{O}}({n^2}/{\epsilon^2})$, which is slower than our accelerated primal-dual stochastic mirror algorithm. Experiments are done using synthetic and real data, and the results match our theoretical rates. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$ for solving OT.} }
Endnote
%0 Conference Paper %T Improved Rate of First Order Algorithms for Entropic Optimal Transport %A Yiling Luo %A Yiling Xie %A Xiaoming Huo %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-luo23a %I PMLR %P 2723--2750 %U https://proceedings.mlr.press/v206/luo23a.html %V 206 %X This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from $\widetilde{\mathcal{O}}({n^{2.5}}/{\epsilon})$ to $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$, where $n$ is the problem size and $\epsilon$ is the accuracy level. In particular, we propose an accelerated primal-dual stochastic mirror descent algorithm with variance reduction. Such special design helps us improve the rate compared to other accelerated primal-dual algorithms. We further propose a batch version of our stochastic algorithm, which improves the computational performance through parallel computing. To compare, we prove that the computational complexity of the Stochastic Sinkhorn algorithm is $\widetilde{\mathcal{O}}({n^2}/{\epsilon^2})$, which is slower than our accelerated primal-dual stochastic mirror algorithm. Experiments are done using synthetic and real data, and the results match our theoretical rates. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$ for solving OT.
APA
Luo, Y., Xie, Y. & Huo, X.. (2023). Improved Rate of First Order Algorithms for Entropic Optimal Transport. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:2723-2750 Available from https://proceedings.mlr.press/v206/luo23a.html.

Related Material