Statistical Optimal Transport

Objective

Matching problems ask: given two sets of random points, what is their minimum cost matching? Such problems lie at the intersection of optimization, probability, and statistics, and have been a rich source of mathematical research for many years. The recent surge of interest in optimal transport has connected this old area to modern machine learning, since matching problems are the core statistical question in optimal transport.

This class will be dedicated to a thorough mathematical exploration of matching problems and their connections to statistical optimal transport, emphasizing areas of ongoing theoretical research.

Planning

Proposed topics :

• Basic structure of matchings, background on optimal transport
• Matchings in dimension d >= 3: the generic case
• Critical dimension 2 and the AKT theorem
• Asymptotic results
•  Lower bounds
•  Extensions to non-compact support
•  Further applications to statistical optimal transport

References

Ajtai, Miklós, János Komlós, and Gábor Tusnády. "On optimal matchings." Combinatorica 4 (1984): 259-264.

Dobri?, V., and Joseph E. Yukich. "Asymptotics for transportation cost in high dimensions." Journal of Theoretical Probability 8 (1995): 97-118

Dudley, Richard Mansfield. "The speed of mean Glivenko-Cantelli convergence." The Annals of Mathematical Statistics 40.1 (1969): 40-50.

Fournier, Nicolas, and Arnaud Guillin. "On the rate of convergence in Wasserstein distance of the empirical measure." Probability Theory and Related Fields 162.3-4 (2015): 707-738.

Leighton, T., and P. Shor. "Tight bounds for minimax grid matching with applications to the average case analysis of algorithms." Combinatorica 9.2 (1989): 161-187.

Talagrand, Michel. Upper and lower bounds for stochastic processes: decomposition theorems. Vol. 60. Springer Nature, 2022.

Weed, Jonathan, and Francis Bach. "Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance." Bernoulli 25.4A (2019): 2620-2648.