Grant: Discovery Grants Program - Individual

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.