Multi-marginal Optimal Transport: Generative models meet Density Functional Theory

多边际最优输运（MOT）是量子化学（QC）和生成模型（GM）中许多关键算法的基础。不幸的是，目前的算法规模指数的边缘的数量，严重限制了实际应用。NSERC Discovery Grant提出了一个跨学科的研究计划，集中在MOT，QC和GM上，旨在构建MOT问题的系统近似，设计算法以突破计算限制，在从业者使用的软件包中实现这些，并在高性能计算和最先进的AI方法方面培训HQP，为他们在计算化学软件开发和人工智能领域的工作做好准备。多边际最优运输（MOT）是一类最优化问题。在其最简单的形式中，在R^N中的概率分布pi（x_1，\dots，x_N）中寻找最优元素，其边际等于给定的一维函数rho_i=rho_1（x_i），i=1，.，N.在这种设置中，最优性意味着某个泛函F = F（pi）在所有pi中是最小的，具有这样的规定的边缘pi->（rho_1，.，rho_N），并且其最小值由F[rho_1，...，rho_N]：= \min{F（pi）：\pi->（rho_1，.，rho_N）}。不幸的是，几个感兴趣的MOT问题不幸地遭受所谓的维数灾难-它们的计算复杂度在边缘数N中呈指数级增长，并且是NP-难的。与N=2边缘理论相反，N>2问题的许多分析和几何方面尚未完全理解。缺乏这样的数学理解限制了严格近似泛函发展的进展，因此，限制了具有MOT理论保证的有效算法的发展，这对于量子化学和生成模型所需的精度水平至关重要。面对这些挑战，我建议开发一种完全不同的方法来处理MOT中的计算和分析问题。我的目标是建立MOT泛函F_ep（pi）的系统近似，正则化强度ep>0。在这类中，极小化的分析性质是很好的理解，允许更有效的计算算法的发展。该提案的主要目的是：（1）发展这种系统近似的数学理论，包括近似误差的量化;（2）基于这些近似设计理论上合理和有效的算法;（3）将理论和算法与计算化学和机器学习相结合。该计划旨在让每个博士和博士后与计算化学家和/或计算机科学家合作。我希望这些合作将有助于博士生和博士后的培训，使他们能够说数学，化学和机器学习的语言。

Multi-marginal Optimal Transport (MOT) underlies many key algorithms in Quantum Chemistry (QC) and Generative Models (GM). Unfortunately, current algorithms scale exponentially in the number of marginals, severely limiting practical applications. This NSERC Discovery Grant proposes an interdisciplinary research program concentrated across MOT, QC and GM, which aims to construct systematic approximations for MOT problems, design algorithms to break through computational limitations, implement these in software packages used by practitioners, and to train HQP in high-performance computing and state-of-the-art AI methods, to prepare them for jobs in computational chemistry software development and AI sector. Multi-marginal Optimal Transport (MOT) is a class of optimization problems. In its simplest form, an optimal element is sought among probability distributions pi(x_1,\dots,x_N) in R^N with marginals equal to given one-dimensional functions rho_i=rho_1(x_i), i=1,...,N. Optimality, in this setup, means that some functional F = F(pi) is minimal among all pi with such prescribed marginals pi->(rho_1,...,rho_N), and its minimal value is indicated by F[rho_1,...,rho_N] := \min{F(pi) : \pi->(rho_1,...,rho_N)}. Unfortunately, several MOT problems of interest unfortunately suffer from the so-called curse of dimensionality --- their computational complexity scales exponentially in the number N of marginals and are NP-hard. In contrast to the N=2 marginals theory, many analytical and geometrical aspects of N>2 problems are not fully understood. The lack of such a mathematical understanding limits the progress of the development of rigorous approximation functionals and, therefore, limits the development of efficient algorithms with theoretical guarantees for MOT, which are fundamental for the level of accuracy required in quantum chemistry and generative models. Faced with these challenges, I propose to develop a radically different approach to deal with computational and analytical issues in MOT. I aim to build systematic approximations of MOT functionals F_ep(pi) with a regularization strength ep>0. In that class, analytical properties of the minimizer are well understood, allowing the development of more efficient computational algorithms. The main aims of this proposal are: (1) to develop a mathematical theory of such systematic approximations, including a quantification of the approximation error; (2) to design theoretically justified and efficient algorithms based on these approximations; (3) to integrate the theory and algorithms with Computational Chemistry and Machine Learning. The program is designed to allow each PhD and PostDoc to collaborate with computational chemists and/or computer scientists. I expect that these collaborations will contribute in the PhD students' and PostDocs' training, allowing them to speak the languages of Mathematics, Chemistry and Machine Learning.