Math 217, Spring 2022
Topics in Applied Mathematics: Optimal Transport

Lectures: 1:00 pm - 1:50, pm MWF, AP&M 5402
Instructor: Bo Li (Office: AP&M 5723. Office phone: (858) 534-6932. Email: bli@math.ucsd.edu)
Office hours: 2:00 - 2:45 Wednesdays and Fridays, or by appointment.

Course Description

This course focuses on applied and computational aspects of optimal transport (OT). It will cover:
  • Monge and Kantorovich formulations of the OT problem. Duality. Existence results. Wasserstein metric.
  • Regularization of the discrete OT problem. Numerical methods, stability and convergence.
  • Gradient flow with the Wasserstein metric. Fokker-Planck equation and other evolutionary equations.
  • Some applications in machine learning and molecular dynamics.
While not required, some background of optimization and measure theory will be helpful. No knowledge in the related application areas is assumed.

Lecture Notes

  • Lecture 1: Course description. Monge's and Kontorovich's formulations of the discrete OT problem.
  • Lecture 2: Kantorovich OT as linear programming. Monge vs. Kantorovich.
  • Lecture 3: Wasserstein metric (W-metric) for discrete OT.
  • Lecture 4: W-metric with the discrete metric matrix. Discrete OT: W-metric is equivalent to Euclid matric.
  • Lecture 5: Duality - weak and strong. The complementarity condition.
  • Lecture 6: Measure-theoretical descriptions of the OT problem in Monge's and Katorovich's forms.
  • Lecture 7: Entropy regularization. Kullback-Leibler divergence. General regularized OT.
  • Lecture 8: Sinkhorn's Theorem on matrix rescaling. Uniqueness.
  • Lecture 9: Sinkhorn's algorithm: Convergence.
  • Lecture 10: Sinkhorn's algorithm: convergence rate via Hilbert's metric. Franklin-Lorenz theorem.
  • Lecture 11: Sinkhorn's algorithm: Overflow instability. Log-domain algorithm.
  • Lecture 12: Continuous OT: Monge's and Kantorovich's formulations. Exampls. M. vs. K.
  • Lecture 13: Properties of transport maps and plans. Existence Theorem. Direct methods.
  • Lecture 14: Narrow topology for probability measures. Weak lower semicontinuity of K-cost functional.
  • Lecture 15: Ulam's Lemma. Prokhorov's Theorem. Narrow compactness of the set of transport plans.
  • Lecture 16: Wasserstein metric. Some examples.
  • Lecture 17: An elementary proof of the triangle inequality. The beta-metric.
  • Lecture 18: Completeness and compactness of the W-metric. An example.
  • Lecture 19: Separability of the W-metric.
  • Lecture 20: Characterization of the convergence w.r.t. the W-metric.
  • Lecture 21: The JKO scheme for heat equation and Fokker-Planck equaiton: steepest descent in W-metric.
  • Lecture 22: Proof of the convergence of the JKO scheme.
  • Lecture 23: Dual problem. Weak duality. Kantorovich (strong) duality.
  • Lecture 24: Proof of the Kantorovich duality for compact Polish spaces.
  • Lecture 25: The Kantorovich-Rubinstein Theorem. c-concave functions.
  • Lecture 26: Existence and characterization of optimal transport maps: Brenier-Knott-Smith theorem.
  • Lecture 27: Support of optimal transport plan is c-cyclically monotone.
  • Lecture 28: c-subdifferentials. Generalized Rockafellar Theorem.
  • Lecture: Dynamic formulation of optimal transport.

References

  1. L. Ambrosio, E. Brue, and D. Semola, Lectures on Optimal Transport, Springer, 2021.
  2. L. Ambrosio, N. Gigli, and G. Savare, Gradient Flows in Metric Spaces and in the Space of Probability Measures, 2nd ed., Birkhauser, 2008. (UCSD e-version available.)
  3. L. Ambrosio and N. Gigli, A User's Guide to Optimal Transport, in Modelling and Optimisation of Flows on Networks, Editors: B. Piccoli and M. Rascle, Lecture Notes in Mathematics 2062, Springer, 2010. (UCSD e-version available.)
  4. A. Figalli and F. Glaudo, An Invitation to Optimal Transport, Wasserstein Distances, and Gradient Flows, EMS Press, 2021.
  5. G. Peyre and M. Cuturi, Computational Optimal Transport, Foundations and Trends in Machine Learning, Vol. 11, No. 5-6, pp. 355-607, 2019. (E-version available for UCSD.)
  6. S. T. Rachev and L. Ruschendorf, Mass Transportation Problems: Volume I: Theory, Springer, 1998. (E-version available for UCSD.)
  7. S. T. Rachev and L. Ruschendorf, Mass Transportation Problems: Volume II: Applications, Springer, 1998. (E-version available for UCSD.)
  8. F. Santambrogio, Optimal Transport for Applied Mathematicians, Birkhauser, 2015. (UCSD e-version available.)
  9. C. Villani, Topics in Optimal Transportation, Amer. Math Soc., 2003.
  10. C. Villani, Optimal Transport, Springer, 2009. (UCSD e-version available.)
Some related research papers will be discussed.

Expected Work for Students

Students are expected to participate in class discussions and possibly read some papers with brief oral report in class.

Last updated by Bo Li on May 3, 2022.