Coursebooks

Computational Optimal Transport

EE-622

Lecturer(s) :

Frossard Pascal
Peyré Gabriel

Language:

English

Frequency

Only this year

Remarque

Only this year: 24th, 25th, 26th June, 2019

Summary

In this short course, I will review numerical approaches for the approximate resolution of optimization problems related to optimal transport. I will also give some insight on how to apply these methods to imaging sciences and machine learning problems.

Content

Optimal transport (OT) has become a fundamental mathematical tool at the interface between calculus of variations, partial differential equations and probability. It took however much more time for this notion to become mainstream in numerical applications. This situation is in large part due to the high computational cost of the underlying optimization problems. There is a recent wave of activity on the use of OT-related methods in fields as diverse as computer vision, computer graphics, statistical inference, machine learning and image processing.


In this short course, I will review numerical approaches for the approximate resolution of optimization problems related to optimal transport. I will also give some insight on how to apply these methods to imaging sciences and machine learning problems. The course will feature a numerical session using Python. Material for the course (including a small book, slides
and computational resources) can be found online at https://optimaltransport.github.io/.

Course 1: Foundations of Optimal Transport


- The basics of Optimal Transport
- Overview of applications in imaging and learning
- Special cases: 1-D, Gaussians
- Network flows solvers
- Semi-discrete, auction


Course 2: Entropic regularization


- Regularization and approximation
- Sinkhorn's algorithm
- Hilbert's metric, Perron-Frobenius
- Extensions: multimarginal, unbalanced


Course 3: Variational Wasserstein problems


- Wasserstein barycenters
- Gradient flows
- Gromov-Wasserstein


Course 4: Density fitting and generative modeling


- Statistical divergences
- Sample complexity
- Minimum Kantorovich Estimator
- Deep learning and generative models

Note

Students will be required to bring their own laptops to the lab session with an updated version of Python 3 installed via an Anaconda distribution (installation instructions can be found at docs.anaconda.com/anaconda/install/).

Keywords

Learning Outcomes

By the end of the course, the student must be able to:

Assessment methods

Project report.

Resources

Bibliography

Gabriel Peyré and Marco Cuturi, Computational Optimal Transport, ArXiv:1803.00567, 2018.

Websites

In the programs

  • Electrical Engineering (edoc), 2018-2019
    • Semester
    • Exam form
      Project report
    • Credits
      1
    • Subject examined
      Computational Optimal Transport
    • Number of places
      60
    • Lecture
      13 Hour(s)
    • Practical work
      4 Hour(s)

Reference week

Lecture
Exercise, TP
Project, other

legend

  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German