November 4, 2021 10:36
Talk by Dr. Boris Muzellec, INRIA on “Breaking the curse of dimensionality in smooth optimal transport” thumbnails


Title: Breaking the curse of dimensionality in smooth optimal transport

It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimensionality. While recent works were able to leverage smoothness to improve the rate of estimation, the computational complexity of the resulting methods still degrades exponentially with the dimension.

In this talk, we show how to leverage smoothness using a kernel sum-of-squares representation of the dense set of inequalities satisfied by optimal transport. Using this technique, we propose a polynomial-time algorithm that results in estimation rates that do not depend on the dimension – at the price of constants that may still depend exponentially on the dimension, in the worst case.

Boris Muzellec,

Related Laboratories

last updated on November 16, 2021 10:20Laboratory