论文标题
大规模最佳运输的数值方法
Numerical Methods for Large-Scale Optimal Transport
论文作者
论文摘要
最佳传输（OT）问题是具有线性编程形式的经典优化问题。机器学习应用程序在其解决方案中提出了新的计算挑战。特别是，OT问题定义了以概率分布为模型的现实世界对象（例如图像，视频，文本等）之间的距离。在这种情况下，相应优化问题的大维度不允许应用经典方法，例如网络单纯形或内点方法。通过引入熵正则化并使用有效的sndhorn算法来解决正则化问题，克服了这一挑战。灵活的替代方法是加速的原始双梯度方法，可以使用任何强键正则化。我们讨论了这些算法和其他相关问题，例如将Wasserstein Barycenter以及其解决方案（包括分散的分布式算法）的有效算法以及有效的算法进行讨论。
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.
