Optimisation stochastique pour le transport optimal à grande échelle.

Résumé Le transport optimal (OT) définit un cadre puissant pour comparer des distributions de probabilité d'une manière géométriquement fidèle. Cependant, l'impact pratique de l'OT est encore limité en raison de sa charge de calcul. Nous proposons une nouvelle classe d'algorithmes d'optimisation stochastique pour faire face aux problèmes à grande échelle couramment rencontrés dans les applications d'apprentissage automatique. Ces méthodes sont capables de manipuler des distributions arbitraires (discrètes ou continues) en ayant simplement besoin de pouvoir en tirer des échantillons, ce qui est la configuration typique des problèmes d'apprentissage à haute dimension. Cela allège la nécessité de discrétiser ces densités, tout en donnant accès à des méthodes à convergence prouvée qui produisent la distance correcte sans erreur de discrétisation. Ces algorithmes reposent sur deux idées principales : (a) le problème OT dual peut être reformulé comme la maximisation d'une espérance . (b) la régularisation entropique du problème OT primaire donne lieu à une optimisation duale lisse qui peut être traitée par des algorithmes dont la convergence est prouvée comme étant plus rapide. Nous instantions ces idées dans trois configurations différentes : (i) en comparant une distribution discrète à une autre, nous montrons que les schémas d'optimisation stochastique incrémentale peuvent battre l'algorithme de Sinkhorn, l'actuel solveur d'OT en dimension finie de pointe. (ii) lors de la comparaison d'une distribution discrète à une densité continue, une reformulation semi-discrète du programme dual se prête à la descente de gradient stochastique moyennée, ce qui conduit à de meilleures performances que la résolution approximative du problème par discrétisation. (iii) lorsqu'il s'agit de deux densités continues, nous proposons une descente de gradient stochastique sur un espace de Hilbert à noyau reproducteur (RKHS). C'est actuellement la seule méthode connue pour résoudre ce problème, à part le calcul de l'OT sur des échantillons finis. Nous soutenons ces affirmations sur un ensemble de problèmes de référence discrets, semi-discrets et continus.