PIMS- IFDS- NSF Summer School on Optimal Transport

Gross substitutes is a fundamental property in mathematics, economics and computation, almost as important as convexity. It is at the heart of optimal transport theory – although this is often underrecognized – and understanding the connection key to understanding the extension of optimal transport to other models of matching.

Lecture 1. (video ) Introduction to gross substitutes M-matrices and M-maps, nonlinear Perron-Froebenius theory, convergence of Jacobi algorithm. A toy hedonic model.

Lecture 2. (video ) Models of matching with transfers Problem formulation, regularized and unregularized case. IPFP and its convergence. Existence and uniqueness of an equilibrium. Lattice structure.

Lecture 3. (video ) Models of matching without transfers Gale and Shapley’s stable matchings. Adachi’s formulation. Kelso-Craford. Hatfield-Milgrom.

In the lectures we will discuss recent results obtained on interface motions in the framework of optimal transport. We intend to (time allowing) discuss the following problems:

The Hele-Shaw type flows in the context of tumor growth. Here the flow describe the growth of tumor cells with contact inhibition. The tumor cells then form a congested zone, which evolves by the pressure generated by the constraint on maximal density. We start with a simple mechanical model, and discuss the effects of nutrients and surface tension in the context of minimizing movements. While the well-posedness would be established by minimizing movements, we will also explore qualitative properties of solutions such as regularity of the interface.

The Stefan problem, in the framework of optimal stopping time. Our focus will be on the well-posedness of the supercooled Stefan problem, which describes freezing of supercooled fluid. The interface between the fluid and ice, as it freezes, exhibits a high degree of irregularity. Our goal is to introduce a notion of solutions that are physically meaningful and stable. We will start with a quick introduction of the necessary background on the optimal stopping time between probability measures. We will establish the well-posedness, and discuss qualitative behavior of solutions.

Videos

• Lecture 1
• Lecture 2
• Lecture 3

Slides

• Slides 1
• Slides 2

In this lecture series we present an overview of dynamical optimal transport and some of its applications to discrete probability and non-commutative analysis. Particular focus is on gradient structures and functional inequalities for dissipative quantum systems, and on homogenisation results for dynamical optimal transport.

Videos

• Lecture 1
• Lecture 2
• Lecture 3

In this mini-course, we shall explain the variational approach to regularity theory for optimal transportation introduced in [8]. This approach does completely bypass the celebrated regularity theory of Caffarelli [2], which is based on the regularity theory for the Monge-Amp ere equation as a fully nonlinear elliptic equation with a comparison principle. Nonetheless, one recovers the same partial regularity theory [5, 4].

The advantage of the variational approach resides in its robustness regarding the regularity of the measures, which can be arbitrary measures [7][Theorem 1.4], and in terms of the problem formulation, e.g. by its extension to almost minimizers [10]. The former for instance is crucial in order to tackle the widely popular matching problem [3, 1] e.g. the optimal transportation between (random) point clouds, as carried out in [7, 6, 9]. The latter is convenient when treating more general than square Euclidean cost functions.

The variational approach follows de Giorgi’s philosophy for minimal surfaces. At its core is the approximation of the displacement by the gradient of a harmonic function. This approximation is based on the Eulerian formulation of optimal transportation, which reveals its strict convexity and the proximity to the $H^{-1}$-norm. In this mini-course, we shall give a pretty self-contained derivation of this harmonic approximation result, and establish applications to the matching problem.

References

• [1] L. Ambrosio, F. Stra, D. Trevisan: A PDE approach to a 2-dimensional matching problem. Probab. Theory Relat. Fields 173, 433–477 (2019).
• [2] L.A. Caffarelli: The regularity of mappings with a convex potential. Journal of the American Mathematical Society 5 (1992), no. 1, 99–104.
• [3] S. Caracciolo, C. Lucibello, G. Parisi, G. Sicuro: Scaling hypothesis for the Euclidean bipartite matching problem. Physical Review E, 90(1), 2014.
• [4] G. De Philippis, A. Figalli: Partial regularity for optimal transport maps. Publications Mathématiques. Institut de Hautes Études Scientifiques 121 (2015), 81–112.
• [5] A. Figalli, Y.-H. Kim: Partial regularity of Brenier solutions of the Monge-Amépre equation. Discrete and Continuous Dynamical Systems (Series A) 28 (2010), 559–565.
• [6] M. Goldman, M. Huesmann: A fluctuation result for the displacement in the optimal matching problem. arXiv e-prints, May 2021. arXiv:2105.02915.
• [7] M. Goldman, M. Huesmann, F. Otto: Quantitative linearization results for the Monge-Amp`ere equation. Communications on Pure and Applied Mathematics (2021).
• [8] M. Goldman, F. Otto: A variational proof of partial regularity for optimal transportation maps. Annales Scientifiques de l’Ećole Normale Supérieure. Quatriéme Série 53 (2020), no. 5, 1209–1233.
• [9] M. Huesmann, F. Mattesini, F. Otto: There is no stationary cyclically monotone Poisson matching in 2d. arXiv e-prints, September 2021. arXiv:2109.13590.
• [10] F. Otto, M. Prod’homme, T. Ried: Variational approach to regularity of optimal transport maps: general cost functions. (English summary) Ann. PDE 7 (2021), no. 2, Paper No. 17, 74 pp.

Videos

• Lecture 1
• Lecture 2
• Lecture 3

Slides & Notes

• Slides
• Lecture Notes

Optimal transport (OT) has recently gained lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension. In this course, I will explain how to leverage entropic regularization methods to define computationally efficient loss functions, approximating OT with a better sample complexity. More information and references can be found on the website of our book “Computational Optimal Transport”.

• Lecture 1
• Lecture 2
• Lecture 3

New measurement technologies like single-cell RNA sequencing are bringing ‘big data’ to biology. One of the most exciting prospects associated with this new trove of data is the possibility of studying temporal processes, such as differentiation and development. In this talk, we introduce the basic elements of a mathematical theory to answer questions like How does a stem cell transform into a muscle cell, a skin cell, or a neuron? How can we reprogram a skin cell into a neuron? We model a developing population of cells with a curve in the space of probability distributions on a high-dimensional gene expression space. We design algorithms to recover these curves from samples at various time-points and we collaborate closely with experimentalists to test these ideas on real data.

Videos

• Lecture 1

Slides

• Slides