  The optimal transport (OT) problem is a classical optimization problem having
the form of linear programming. Machine learning applications put forward new
computational challenges in its solution. In particular, the OT problem defines
a distance between real-world objects such as images, videos, texts, etc.,
modeled as probability distributions. In this case, the large dimension of the
corresponding optimization problem does not allow applying classical methods
such as network simplex or interior-point methods. This challenge was overcome
by introducing entropic regularization and using the efficient Sinkhorn's
algorithm to solve the regularized problem. A flexible alternative is the
accelerated primal-dual gradient method, which can use any strongly-convex
regularization. We discuss these algorithms and other related problems such as
approximating the Wasserstein barycenter together with efficient algorithms for
its solution, including decentralized distributed algorithms.
