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

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

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.