论文标题
多项式时间算法，用于与结构的多边界最佳运输问题
Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure
论文作者
论文摘要
由于机器学习，统计和科学的应用，多边缘最佳运输（MOT）引起了极大的兴趣。但是，在大多数应用中，MOT的成功受到缺乏有效算法的严重限制。实际上，MOT一般需要在边际K及其支撑大小n的数量中指数时间n。本文开发了一种关于“结构”在poly（n，k）时间中可溶解的一般理论。 我们开发了一个统一的算法框架，用于通过表征不同算法所需的“结构”来解决poly（n，k）时间中的MOT，以双重可行性甲骨文的简单变体所需的“结构”。该框架有几个好处。首先，它使我们能够证明当前是最流行的MOT算法的Sinkhorn算法比其他算法要在poly（n，k）时间中求解MOT的结构更严格。其次，我们的框架使为给定的MOT问题开发Poly（N，K）时间算法变得更加简单。特别是（大约）求解双重可行性甲骨文是必要和足够的 - 这更适合标准算法技术。 我们通过为三个通用类成本结构的poly（n，k）时间算法开发poly（n，k）时间算法来说明这种易用性：（1）图形结构； （2）设定优化结构； （3）低阶和稀疏结构。对于结构（1），我们恢复了已知的结果，即sindhorn具有poly（n，k）运行时；此外，我们为计算精确且稀疏的解决方案提供了第一个poly（n，k）时间算法。对于结构（2） - （3），我们给出了第一个poly（n，k）时间算法，即使用于近似计算。这三个结构一起涵盖了许多MOT的当前应用。
Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly(n,k) time. We develop a unified algorithmic framework for solving MOT in poly(n,k) time by characterizing the "structure" that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly(n,k) time. Second, our framework makes it much simpler to develop poly(n,k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle -- which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing poly(n,k) time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly(n,k) runtime; moreover, we provide the first poly(n,k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n,k) time algorithms, even for approximate computation. Together, these three structures encompass many -- if not most -- current applications of MOT.
