View abstract

Session III.3 - Computational Optimal Transport

Tuesday, June 20, 17:30 ~ 18:00

Exponential convergence of Sinkhorn algorithm for quadratic costs and weakly log- concave marginals

Giovanni Conforti

IPParis, FRANCE   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Over the past decade, Entropic Optimal Transport problem has emerged as a versatile and computationally more tractable proxy for the Optimal Transport (Monge-Kantorovich) problem for applications in data science and statistical machine learning. One of the reasons behind the interest in adding an entropic penalty in the Monge Kantorovich problem is the fact that solutions can be computed by means of Sinkhorn’s algorithm, a.k.a. Iterative Proportional Fitting Procedure. While the exponential convergence of Sinkhorn’s iterates is well understood in a discrete setting or for compactly supported measures and bounded costs, when moving to unbounded costs and non compact marginals the picture is far less clear. In this talk, we shall present an exponential convergence result in the landmark example of quadratic entropic optimal transport and approximately log-concave marginals. The main innovation in the proof strategy are new propagation of weak convexity results along Hamilton Jacobi Bellman equations, that may be of independent interest.

Joint work with Alain Durmus (IPParis), Giacomo Greco (TU Eindhoven) and Maxence Noble (IPParis).

View abstract PDF