Collaborative Research: AF: Small: Efficient Algorithms for Optimal Transport in Geometric Settings

合作研究：AF：小：几何设置中最佳传输的高效算法

• 批准号: 2223870
• 负责人: Pankaj Agarwal
• 金额: $ 31.59万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2223870&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Efficient

Optimal transport (OT) is a powerful tool for comparing probability distributions and computing maps between them. Simply put, optimal transport is the minimum-cost plan to transport mass from one distribution to the other, where the cost of transporting one unit of mass between two locations is the ground distance between the two locations. OT has been studied extensively in mathematics, engineering, physics, economics, operations research, and computer science because of their numerous applications. Despite extensive work, computing OT plans has remained a computationally challenging problem, and there is a large gap between the theory and practice of OT algorithms. The need for fast OT algorithms is becoming even more urgent with the proliferation of machine learning and algorithmic decision making in all disciplines. The scarcity of scalable algorithms that compute high quality transport plans has limited the applicability OT to many applications. The main goal of this project is to advance the theoretical underpinnings of OT and to bridge the gap between the theory and practice of OT algorithms. By exploiting combinatorial, geometric and statistical properties of OT, leveraging new approaches for min-cost flow, and exploiting approximation and probabilistic techniques, simple and scalable algorithms will be developed for computing high quality OT plans of both discrete and continuous distributions whose supports are compact regions in Euclidean space. The emphasis will be on designing combinatorial algorithms that not only have good worst-case running time but that have better expected running time on stochastic or semi-stochastic inputs. The project will also explore techniques to circumvent the curse of dimensionality, which arises in the OT of high-dimensional distributions. Building on these OT algorithms, new algorithms will be developed for data analysis (e.g. clustering, training neural networks) on a family of distributions in Wasserstein space, i.e., using OT as the distance between a pair of distributions; for quality assessment of algorithms that return a probability distribution (e.g., flood-risk-analysis algorithms that return a distribution of water over a region).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

最优传输 (OT) 是比较概率分布和计算概率分布之间的映射的强大工具。简而言之，最佳运输是将质量从一个分布运输到另一个分布的最低成本计划，其中在两个位置之间运输一个单位质量的成本是两个位置之间的地面距离。由于其众多的应用，OT 在数学、工程、物理、经济学、运筹学和计算机科学领域得到了广泛的研究。尽管进行了大量的工作，计算 OT 计划仍然是一个计算上具有挑战性的问题，并且 OT 算法的理论和实践之间存在很大差距。随着机器学习和算法决策在所有学科中的普及，对快速 OT 算法的需求变得更加迫切。计算高质量运输计划的可扩展算法的稀缺限制了 OT 在许多应用中的适用性。该项目的主要目标是推进 OT 的理论基础并弥合 OT 算法的理论与实践之间的差距。通过利用 OT 的组合、几何和统计特性，利用最小成本流的新方法，并利用近似和概率技术，将开发简单且可扩展的算法，用于计算支持紧凑的离散和连续分布的高质量 OT 计划欧几里得空间中的区域。重点是设计组合算法，该算法不仅具有良好的最坏情况运行时间，而且在随机或半随机输入上具有更好的预期运行时间。 该项目还将探索规避高维分布 OT 中出现的维度灾难的技术。在这些 OT 算法的基础上，将开发新的算法，用于对 Wasserstein 空间中的一系列分布进行数据分析（例如聚类、训练神经网络），即使用 OT 作为一对分布之间的距离；用于对返回概率分布的算法（例如，返回某个区域的水分布的洪水风险分析算法）进行质量评估。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优势进行评估，被认为值得支持以及更广泛的影响审查标准。

项目成果

Improved ε-Approximation Algorithm for Geometric Bipartite Matching

改进的几何二分匹配的 ε 近似算法

• 发表时间: 2022-07
• 期刊: Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory
• 作者: Pankaj K. Agarwal; Sharath Raghvendra
• 通讯作者: Sharath Raghvendra

A Higher Precision Algorithm for Computing the 1-Wasserstein Distance

一种计算1-Wasserstein距离的高精度算法

• 发表时间: 2023-04
• 期刊: Proc. 11th International Conference on Learning Representations
• 作者: Pankaj K Agarwal; Sharath Raghvendra
• 通讯作者: Sharath Raghvendra

Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching

确定性、近线性 ?

• DOI: 10.1145/3519935.3519977
• 发表时间: 2022-06
• 期刊: ACM Symposium on Theory of Computing
• 作者: Agarwal, Pankaj K.;Chang, Hsien;Raghvendra, Sharath;Xiao, Allen
• 通讯作者: Xiao, Allen