检索结果-内蒙古大学图书馆

Polynomial-time algorithms for multimarginal optimal transport problems with structure

MATHEMATICAL programming 2023年第1-2期199卷 1107-1178页

作者： Altschuler, Jason M. Boix-Adsera, Enric MIT Lab Informat & Decis Syst LIDS 77 Massachusetts Ave Cambridge MA 02139 USA

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-ofuse 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.

关键词： Multimarginal optimal transport Polynomial-time algorithms implicit linear programming Structured linear programs

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：