权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
2223871
负责人：
Sharath Raghvendra
金额：
$ 30.8万
依托单位：
Virginia Polytechnic Institute and State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-06-15 至 2025-05-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2223871&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作为一对分布之间的距离；用于返回概率分布的算法的质量评估（例如，返回一个地区的水分布的洪水风险分析算法）。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。