Algorithms for Euclidean-Regularised Optimal Transport

Authors

Dmitry A. Pasechnyuk, Mohamed Bin Zayed University of Artificial IntelligenceFollow
Michael Persiianov, Moscow Institute of Physics and Technology
Pavel Dvurechensky, Weierstrass Institute for Applied Analysis and Stochastics
Alexander Gasnikov, Moscow Institute of Physics and Technology

Document Type

Conference Proceeding

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Abstract

This paper addresses the Optimal Transport problem, which is regularized by the square of Euclidean ℓ2 -norm. It offers theoretical guarantees regarding the iteration complexities of the Sinkhorn–Knopp algorithm, Accelerated Gradient Descent, Accelerated Alternating Minimisation, and Coordinate Linear Variance Reduction algorithms. Furthermore, the paper compares the practical efficiency of these methods and their counterparts when applied to the entropy-regularized Optimal Transport problem. This comparison is conducted through numerical experiments carried out on the MNIST dataset.

First Page

84

Last Page

98

DOI

10.1007/978-3-031-47859-8_7

Publication Date

11-10-2023

Keywords

Alternating optimisation, Euclidean regularisation, Optimal transport, Primal-dual algorithm, Sinkhorn algorithm

Comments

IR conditions: non-described

Recommended Citation

D. Pasechnyuk, M. Persiianov, P. Dvurechensky and A. Gasnikov, "Algorithms for Euclidean-Regularised Optimal Transport," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 14395 LNCS, pp. 84 - 98, Nov 2023. doi: 10.1007/978-3-031-47859-8_7