Center for Advanced Intelligence Project

Title: Breaking the curse of dimensionality in smooth optimal transport

Abstract:
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.

Bio:
Boris Muzellec, https://borismuzellec.github.io/