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

多边际最优输运（MOT）是量子化学（QC）和生成模型（GM）中许多关键算法的基础。不幸的是，目前的算法在边际数量上呈指数级增长，严重限制了实际应用。这项NSERC发现基金提出了一个跨学科的研究项目，集中在MOT， QC和GM，旨在构建MOT问题的系统近似，设计算法以突破计算限制，在从业者使用的软件包中实现这些，并培训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 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.