A contribution to Optimal Transport on incomparable spaces

Optimal Transport is a theory that allows to define geometrical notions of distance between probability distributions and to find correspondences, relationships, between sets of points. Many machine learning applications are derived from this theory, at the frontier between mathematics and optimization. This thesis proposes to study the complex scenario in which the different data belong to incomparable spaces. In particular we address the following questions: how to define and apply the optimal transport between graphs, between structured data? How can it be adapted when the data are varied and not embedded in the same metric space? This thesis proposes a set of Optimal Transport tools for these different cases. An important part is notably devoted to the study of the Gromov-Wasserstein distance whose properties allow to define interesting transport problems on incomparable spaces. More broadly, we analyze the mathematical properties of the various proposed tools, we establish algorithmic solutions to compute them and we study their applicability in numerous machine learning scenarii which cover, in particular, classification, simplification, partitioning of structured data, as well as heterogeneous domain adaptation.Le Transport Optimal est une théorie permettant de définir des notions géométriques de distance entre des distributions de probabilité et de trouver des correspondances, des relations, entre des ensembles de points. De cette théorie, à la frontière entre les mathématiques et l'optimisation, découle de nombreuses applications en machine learning. Cette thèse propose d'étudier le scénario, complexe, dans lequel les différentes données appartiennent à des espaces incomparables}. En particulier nous abordons les questions suivantes : comment définir et appliquer le transport optimal entre des graphes, entre des données structurées ? Comment l'adapter lorsque les données sont variées et ne font pas partie d'un même espace métrique ? Cette thèse propose un ensemble d'outils de Transport Optimal pour ces différents cas. Un important volet est notamment consacré à l'étude de la distance de Gromov-Wasserstein dont les propriétés permettent de définir d'intéressants problèmes de transport sur des espaces incomparables. Plus largement, nous analysons les propriétés mathématiques des différents outils proposés, nous établissons des solutions algorithmiques pour les calculer et nous étudions leur applicabilité dans de nombreux scenarii de machine learning qui couvrent, notamment, la classification, la simplification, le partitionnement de données structurées, ainsi que l'adaptation de domaines hétérogènes