Aller au contenu  Aller au menu  Aller à la recherche

Bienvenue - Laboratoire Jacques-Louis Lions




Paris Cité
Print this page |
Internships (10th and 11th grades high school students)
Job shadowing (Year 10, Year 11 students) See

Key figures

Key figures

189 people work at LJLL

86 permanent staff

80 researchers and permanent lecturers

6 engineers, technicians and administrative staff

103 non-permanent staff

74 Phd students

15 post-doc and ATER

14 emeritus scholars and external collaborators


January 2022


Jean Feydy

Monday 6 May 2019

Jean Feydy (ENS de Paris et ENS de Paris-Saclay)

Discrete Optimal Transport : progress and perspectives

Abstract : Computing distances between weighted point clouds is a fundamental problem in applied mathematics, with applications ranging from Computer Vision (SLAM, reconstruction from LIDAR...) to Medical Imaging (image, mesh, fiber track registration) and Machine Learning (GANs, VAEs, geometric deep learning...).

In practice, researchers strive to endow spaces of measures with distances that must :

  • Lift a ground metric defined on R^d as faithfully as possible ;
  • Define informative gradients with respect to the points’ weights and positions ;
  • Be affordable, from a computational point of view.

In this talk, I will first present the three families of distances that have shaped the literature since the 50’s :

  • Soft-Hausdorff (aka. ICP, GMM-loglikelihood) losses, which rely on (soft) nearest-neighbour projections.
  • Kernel (aka. Sobolev, Electrostatic, MMD, blurred SSD) norms, which rely on (discrete) convolutions.
  • Optimal Transport (OT, aka. Earth-Mover, Wasserstein, Linear Assignment) costs, which often rely on linear or convex optimizers.

Focusing on OT, which is most appealing from a geometric perspective, I will then explain how to compute Wasserstein distances *efficiently*.
Leveraging recent works (2016+) on entropic regularization, we will see that fast multiscale strategies now allow us to compute smooth, approximate solutions of the OT problem with strong theoretical guarantees. As evidenced by a live demonstration of the GeomLoss python library :
on modern gaming hardware, Wasserstein distances (and gradients !) can now be computed between millions of samples in a matter of seconds.

Available through efficient ( log-linear), robust and well-packaged GPU routines, Wasserstein distances can now be used as a drop-in replacement for the cheaper Hausdorff and Kernel distances. But how useful can this tool be in applied settings ? To conclude this talk, I will present open problems related to OT theory and, more generally, to geometric data analysis :

  • the link between entropic regularization, de-biasing and low-frequency OT ;
  • the convergence of annealing schemes for transport problems ;
  • the gap between Kernel/OT losses and generic dual norms, known as Adversarial Networks in the recent machine learning literature ;
  • the distinction between "geometric" and "pointwise" learning problems.

References :

  1. "The invisible hand algorithm : Solving the assignment problem with statistical physics", Kosowsky and Yuille, Neural Networks, 1994.
  2. "Computational Optimal Transport", Peyré and Cuturi, , 2018.
  3. "Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems", Schmitzer, 2016.
  4. "Global divergences between measures : from Hausdorff distance to Optimal Transport", Feydy and Trouvé, ShapeMI 2018.
  5. "Interpolating between Optimal Transport and MMD using Sinkhorn Divergences", Feydy, Séjourné, Vialard, Amari, Trouvé, Peyré, AiStats 2019.