A Graph Theoretic Additive Approximation of Optimal Transport
A Graph Theoretic Additive Approximation of Optimal Transport
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Nathaniel Lahn;Deepika Mulchandani;S. Raghvendra
中科院分区：
文献类型：
--
作者：
Nathaniel Lahn;Deepika Mulchandani;S. Raghvendra
运输成本是一个有吸引力的概率分布之间的相似性度量，由于其许多有用的理论性质。然而，精确地解决最佳运输可能是昂贵的。因此，有显着的努力对可扩展的近似算法的设计。以前的组合结果[Sharathkumar，Agarwal STOC '12，Agarwal，Sharathkumar STOC '14]主要集中在近线性时间乘法近似算法的设计。也有人试图设计具有附加误差的近似解[Cuturi NIPS '13，Altschlaur\埃塔尔\ NIPS '17，Dvurechensky \埃塔尔\，ICML '18，Quanrud，SOSA '19]，在时间范围内，成本矩阵的大小是线性的，多项式为$C/\delta$;这里$C$是成本矩阵中的最大值，$\delta$是附加误差。我们提出了一个适应的Gabow和Tarjan的经典图算法，并提供了一个新的分析，该算法的执行时间由$O（\frac{n^2 C}{\delta}+ \frac{nC^2}{\delta^2}）$。我们的算法非常简单，对于任意小的常数$\vareps $，只执行$\lfloor \frac{2C}{（1-\vareps）\delta}\rfloor + 1$ iterations，其中每次迭代只包括Dijkstra类型的搜索，然后是深度优先搜索。我们还提供了实证结果表明，我们的算法是有竞争力的Sinkhorn算法的执行时间的顺序执行。此外，我们的算法可以快速计算出非常小的$\delta$值的解决方案，而Sinkhorn算法由于数值不稳定而减慢。
Transportation cost is an attractive similarity measure between probability distributions due to its many useful theoretical properties. However, solving optimal transport exactly can be prohibitively expensive. Therefore, there has been significant effort towards the design of scalable approximation algorithms. Previous combinatorial results [Sharathkumar, Agarwal STOC '12, Agarwal, Sharathkumar STOC '14] have focused primarily on the design of near-linear time multiplicative approximation algorithms. There has also been an effort to design approximate solutions with additive errors [Cuturi NIPS '13, Altschuler \etal\ NIPS '17, Dvurechensky \etal\, ICML '18, Quanrud, SOSA '19] within a time bound that is linear in the size of the cost matrix and polynomial in $C/\delta$; here $C$ is the largest value in the cost matrix and $\delta$ is the additive error. We present an adaptation of the classical graph algorithm of Gabow and Tarjan and provide a novel analysis of this algorithm that bounds its execution time by $O(\frac{n^2 C}{\delta}+ \frac{nC^2}{\delta^2})$. Our algorithm is extremely simple and executes, for an arbitrarily small constant $\varepsilon$, only $\lfloor \frac{2C}{(1-\varepsilon)\delta}\rfloor + 1$ iterations, where each iteration consists only of a Dijkstra-type search followed by a depth-first search. We also provide empirical results that suggest our algorithm is competitive with respect to a sequential implementation of the Sinkhorn algorithm in execution time. Moreover, our algorithm quickly computes a solution for very small values of $\delta$ whereas Sinkhorn algorithm slows down due to numerical instability.