论文标题
用于解决最佳传输问题的加速随机算法
An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem
论文作者
论文摘要
提出了具有方差降低算法（PDASGD）的原始二重加速随机梯度下降，以解决线性约束优化问题。 PDASGD可以应用于解决离散的最佳传输（OT）问题，并享受最著名的计算复杂性 - $ \ wideTilde {\ Mathcal {o}}}}（n^2/ε）$，其中$ n $是原子的数量，$ε> 0 $是准确度。在文献中，已经提出了一些原始的双重加速一阶算法，例如APDAGD，并具有$ \ widetilde {\ Mathcal {o}}}（n^{2.5}/ε）$的订单用于解决OT问题。为了了解为什么我们提出的算法可以提高速率$ \ widetilde {\ Mathcal {o}}}（\ sqrt {n}）$，我们的随机算法在求解线性构成优化问题的计算复杂性方面较低。证明OT问题可以满足上述条件。数值实验表明，提出的PDASGD算法的出色实践性能用于解决OT问题。
A primal-dual accelerated stochastic gradient descent with variance reduction algorithm (PDASGD) is proposed to solve linear-constrained optimization problems. PDASGD could be applied to solve the discrete optimal transport (OT) problem and enjoys the best-known computational complexity -- $\widetilde{\mathcal{O}}(n^2/ε)$, where $n$ is the number of atoms, and $ε>0$ is the accuracy. In the literature, some primal-dual accelerated first-order algorithms, e.g., APDAGD, have been proposed and have the order of $\widetilde{\mathcal{O}}(n^{2.5}/ε)$ for solving the OT problem. To understand why our proposed algorithm could improve the rate by a factor of $\widetilde{\mathcal{O}}(\sqrt{n})$, the conditions under which our stochastic algorithm has a lower order of computational complexity for solving linear-constrained optimization problems are discussed. It is demonstrated that the OT problem could satisfy the aforementioned conditions. Numerical experiments demonstrate superior practical performances of the proposed PDASGD algorithm for solving the OT problem.
