March 20, 2018
Faster algorithms for (regularized) Optimal Transport
Pavel Dvurechensky, Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany
Optimal Transport (OT) distances are widely used in Machine Learning, Image Analysis, etc. State-of-the-art approach for solving Optimal Transport problem is Sinkhorn method applied to entropy regularized OT problem. But, to reach good accuracy, the regularization parameter has to be small, which makes Sinkhorn method unstable. We develop an alternative, accelerated-gradient-based, approach and solve OT problem with better theoretical complexity bounds and better performance in practice.
Joint work with A. Gasnikov, S. Omelchenko, and A. Tiurin.