Scientific

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

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.

• Lecture 1
• Lecture 2
• Lecture 3

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. Introduction to gross substitutes M-matrices and M-maps, nonlinear Perron-Froebenius theory, convergence of Jacobi algorithm. A toy hedonic model.

Lecture 2. 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. Models of matching without transfers Gale and Shapley’s stable matchings. Adachi’s formulation. Kelso-Craford. Hatfield-Milgrom.

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. Introduction to gross substitutes M-matrices and M-maps, nonlinear Perron-Froebenius theory, convergence of Jacobi algorithm. A toy hedonic model.

Lecture 2. 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. Models of matching without transfers Gale and Shapley’s stable matchings. Adachi’s formulation. Kelso-Craford. Hatfield-Milgrom.

A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction. The search space for these polynomials is ideal of Grassmann-Plücker relations, which quickly becomes too large to efficiently search, and in most instances where this technique is used, additional assumptions on the structure of the desired polynomial are necessary.

In this talk, I will describe how by changing the search space, we are able to use linear programming to exhaustively search for similar polynomial certificates of non-realizability without any assumed structure. We will see that, perhaps surprisingly, this elementary strategy yields results that are competitive with more elaborate alternatives and allows us to prove non-realizability of several interesting polytopes.