ICMLFeb, 2018
计算最优传输:加速梯度下降比 Sinkhorn 算法更好的复杂度
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
Pavel Dvurechensky, Alexander Gasnikov, Alexey Kroshnin
TL;DR本研究分析了逼近两个离散分布之间的一般最优运输(OT)距离的两种算法,并证明了复杂度界限,其中一种基于 Sinkhorn 算法,另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比,我们的算法具有更好的复杂度界限,更好地依赖于 ε,同时可用于各种正则项。