Bienvenue - Laboratoire Jacques-Louis Lions

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 :
https://www.kernel-operations.io/geomloss/
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, optimaltransport.github.io/book , 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.