Teaching: Computational optimal transport (lecture+exercises)

Overview

• 4 SWS (2h lecture + 2h exercises), credits: 6
• See StudIP for details on time and place.
• The lecture is held in hybrid format, i.e. it can be attended in person or online and recordings will be made available. Interactive participation in the lecture is strongly encouraged.
• The solution to the weekly exercise sheets will be discussed in virtual BBB sessions.
• There will be the option for a weekly in-person discussion session where students are encouraged to ask questions.
• Lanuguage: English

Target audience / what to expect?

This lecture will provide a basic introduction to optimal transport with a focus on the computational/algorithmic side.

• It is primarily addressed at computer science students with an interest in mathematical methods (that may want to prepare for a thesis in our group).
• However, we also invite mathematics students and will provide some additional guidance here and there about the more theoretical aspects.
• The lecture may also be of interest to physics students with an interest in mathematical and computational topics.

Everyone should have a good intuitive grasp on basic mathematics such as linear algebra and (finite-dimensional) analysis. We will encounter concepts like Lagrange multipliers, optimization and algorithmic tools such as Dijkstra's shortest path algorithm. The lecture will contain detailed proofs but these do not play a major role in the exam. The exams will most likely be held orally.

We will closely follow the lecture material with computational examples. For this we will rely mostly on Python. All examples can be run on the GWDG jupyter cloud.

Tentative list of topics

• Kantorovich formulation of optimal transport and basic duality
• Wasserstein distances and displacement interpolation
• classical algorithms such as the Hungarian method and auction algorithm
• entropic regularization and the Sinkhorn algorithm
• prototypical data analysis applications

Literature

• Lecture notes from the previous run
• More mathematical lecture notes from a more advanced course for doctoral students
• Gabriel Peyré, Marco Cuturi: Computational Optimal Transport, Foundations and Trends in Machine Learning, 2019, 11, 355-607 (available online) (introduction with a focus on computational aspects, avoiding mathematical details)
• Filippo Santambrogio: Optimal Transport for Applied Mathematicians, Birkhäuser Boston, 2015 (introduction aimed at applied mathematicians, harder for students)