Advances in Optimal Transport : Low-Rank Structures and Applications in Machine Learning - Centre de recherche en économie et statistique (CREST) Accéder directement au contenu
Thèse Année : 2023

Advances in Optimal Transport : Low-Rank Structures and Applications in Machine Learning

Avancées en Transport Optimal : Structures de Faible Rang et Applications à l'Apprentissage Automatique

Meyer Scetbon
  • Fonction : Auteur
  • PersonId : 1255364
  • IdRef : 26996553X

Résumé

Recent advances in hardware, such as the development of highly-parallel accelerators, and the growing permeabilitybetween computer science, statistics, optimization and applied mathematics have brought forward a new generation of tools,capable of addressing increasingly complex machine learning (ML) problems. Among these new challenges, some require the comparison of point clouds or probability measures. Optimal transport (OT) has become a widely used tool in this context due to its ability to provide a natural geometry in the space of distributions and offer a new perspective for dealing with ML problems when lifted into this space. Starting from a cost function (e.g. a distance) on the space on which measures are supported, OT consists in finding a mapping or coupling between both measures that is optimal with respect to that cost. In other words, OT naturally extends the ground cost between two points to a discrepancy function between histograms of points, or probability measures, in the form of an optimization problem. Further, as a consequence of its strong geometric component, OT is the object of a rich mathematical theory regarding its metric and topological properties, on which ML practitioners can rely to build and study their models.Yet, in their original form, as proposed by Kantorovich, OT distances are not well suited for applied problems: (i) computing OT between discrete distributions amounts to solving a large and expensive network flow problem which requires a supercubic complexity; (ii) estimating OT using sampled measures is doomed by the curse of dimensionality: the sample convergence rate of OT is exponentially slow w.r.t. the dimension of the ambient space, therefore OT is likely to be meaningless when used on samples from high-dimensional densities. Despite these challenges, OT has shown great promise in various machine learning applications, and ongoing research is aimed at addressing these challenges and making OT more accessible and usable in practice.The main approach to alleviate these issues consists in regularizing the optimization problem using an entropic regularization. By adding entropy to the objective function, one can now solves a regularized version of the OT problem in quadratic time and memory using the Sinkhorn algorithm. In addition, this regularization allows to avoid the curse of dimensionality as long as enough entropy has been added.Even though entropic regularization has improved both the computational cost and the statistical properties of optimal transport, it still suffers from a quadratic complexity that prevents its use for large-scale applications. One guiding principle of this thesis is that there are still many research opportunities to develop new algorithmic tools that can exploit or extend this way of thinking in order to make OT applicable to large-scale problems.This thesis consists of two main parts. In the first part, we propose new regularization schemes of the OT problem and its quadratic variant, namely the Gromov-Wasserstein (GW) problem, by considering low-rank factorization of both the underlying cost and the coupling solving the OT problem itself. These new computational schemes pave the way for the use of OT in the large-scale setting. In the second part, we show that OT can also offer new perspective on longstanding ML problems once lifted into the set of distributions. We adopt this point of view on two applied problems in fairness and robustness respectively and propose new approaches to tackle them using OT.
Les progrès récents en matière de matériel informatique, tels que le développement d'accélérateurs hautement parallèles, et la perméabilité croissante entre l'informatique, les statistiques, l'optimisation et les mathématiques appliquées ont donné naissance à une nouvelle génération d'outils capables de résoudre des problèmes d'apprentissage automatique (AA) de plus en plus complexes. Parmi ces nouveaux défis, certains nécessitent la comparaison de nuages de points ou de mesures de probabilité. Le transport optimal (TO) est devenu un outil largement utilisé dans ce contexte en raison de sa capacité à fournir une géométrie naturelle dans l'espace des distributions et à offrir une nouvelle perspective pour traiter les problèmes d'AA lorsqu'ils sont levés dans cet espace. À partir d'une fonction de coût (par exemple, une distance) défini entre les points où sont supportées les mesures, le TO consiste à trouver un couplage entre les deux mesures qui soit optimal par rapport à ce coût. En d'autres termes, le TO étend naturellement le coût entre deux points à coût entre des histogrammes de points, ou des mesures de probabilité, sous la forme d'un problème d'optimisation. De plus, en raison de sa forte composante géométrique, le TO fait l'objet d'une riche théorie mathématique sur laquelle les praticiens peuvent s'appuyer pour construire et étudier leurs modèles.Pourtant, dans leur forme originale, telle qu'elle a été proposée par Kantorovich, les distances de TO ne sont pas bien adaptées aux problèmes appliqués : (i) le calcul du TO entre des mesures discrètes revient à résoudre un programme linéaire coûteux qui requiert une complexité supercubique en le nombre de points; (ii) l'estimation du TO à l'aide de mesures échantillonnées est condamnée par la malédiction de la dimensionnalité, le TO est donc susceptible d'être dépourvue de sens lorsqu'elle est utilisée sur des échantillons provenant de densités en haute dimension. En dépit de ces difficultés, le TO s'est révélée très prometteur dans diverses applications d'AA, et les recherches en cours visent à relever ces défis et à rendre le TO plus accessible et utilisable dans la pratique.La principale approche pour pallier ces problèmes consiste à régulariser le problème d'optimisation en ajoutant un terme d'entropie a l'objectif. En ajoutant de l'entropie, on peut alors résoudre une version régularisée du problème de TO en temps et en mémoire quadratiques à l'aide de l'algorithme de Sinkhorn. De plus, cette régularisation permet d'éviter la malédiction de la dimensionnalité à condition d'avoir ajouté suffisamment d'entropie. Même si la régularisation entropique a amélioré à la fois le coût de calcul et les propriétés statistiques du transport optimal, elle souffre toujours d'une complexité quadratique qui empêche son utilisation pour des applications à grande échelle. Un des principes directeurs de cette thèse est qu'il existe encore de nombreuses opportunités de recherche pour développer de nouveaux outils algorithmiques qui peuvent exploiter ou étendre ce mode de pensée afin de rendre le TO applicable à des problèmes à grande échelle.Cette thèse se compose de deux parties principales. Dans la première partie, nous proposons de nouveaux schémas de régularisation du problème de TO et de sa variante quadratique, à savoir le problème de Gromov-Wasserstein (GW), en considérant des factorisations de bas rang à la fois du coût sous-jacent et du couplage résolvant le problème de TO. Ces nouveaux schémas de calcul ouvrent la voie à l'utilisation du problème TO dans un cadre à grande échelle. Dans la deuxième partie, nous montrons que le TO peut également offrir une nouvelle perspective sur des problèmes d'AA de longue date dès lors qu'ils sont formalisés dans l'espace des distributions. Nous adoptons ce point de vue sur deux problèmes appliqués, à savoir en équité et en robustesse, et proposons de nouvelles approches pour les aborder à l'aide du TO.
Fichier principal
Vignette du fichier
114664_SCETBON_2023_archivage.pdf (15.75 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)

Dates et versions

tel-04100457 , version 1 (17-05-2023)

Identifiants

  • HAL Id : tel-04100457 , version 1

Citer

Meyer Scetbon. Advances in Optimal Transport : Low-Rank Structures and Applications in Machine Learning. Optimization and Control [math.OC]. Institut Polytechnique de Paris, 2023. English. ⟨NNT : 2023IPPAG002⟩. ⟨tel-04100457⟩
262 Consultations
100 Téléchargements

Partager

Gmail Facebook X LinkedIn More