Faster algorithms for (regularized) optimal transport

In this talk I will discuss Optimal Transport (OT) optimization problem, which arises in different machine learning tasks, such as unsupervised learning, semi-supervised learning, clustering, text classification, as long as in image retrieval, clustering and classification, statistics, and other applications. Originally this is a linear programming problem and standard linear programming solvers have complexity proportional to $n^3$, where $n$ is the dimension of the problem. For example, in image analysis $n$ is the number of pixels in the considered picture and can be as large as one million, which makes standard linear programming solvers inapplicable. This motivates the development of alternative algorithms. The state-of-the-art approach for large-scale setting is to apply Sinkhorn's algorithm to the entropy-regularized OT optimization problem. This algorithm has very good performance in practice, but the complexity bound has quite bad dependence on the accuracy of the solution. We propose an alternative algorithm which is based on accelerated gradient descent and allows to solve not only entropy-regularized optimal transport problem, but also OT problem with other regularizers. For our algorithm, we prove complexity bound, which has better than Sinkhorn's algorithm dependence on the accuracy of the solution.