PEYRE Gabriel

Le transport optimal (OT) définit des distances de "Wasserstein" géométriquement significatives, utilisées dans des applications d'apprentissage automatique pour comparer des distributions de probabilité. Cependant, un goulot d'étranglement clé est la conception d'un coût " au sol " qui doit être adapté à la tâche étudiée. Dans la plupart des cas, l'apprentissage métrique supervisé n'est pas accessible, et l'on recourt généralement à une approche ad hoc. L'apprentissage métrique non supervisé est donc un problème fondamental pour permettre des applications du Transport Optimal basées sur les données. Dans cet article, nous proposons pour la première fois une réponse canonique en calculant le coût au sol comme un vecteur propre positif de la fonction reliant un coût aux distances OT par paire entre les entrées. Cette fonction est homogène et monotone, ce qui fait de l'apprentissage métrique non supervisé un problème non linéaire de Perron-Frobenius. Nous fournissons des critères pour assurer l'existence et l'unicité de ce vecteur propre. En outre, nous présentons une méthode de calcul évolutive utilisant la régularisation entropique, qui, dans la grande limite de régularisation, opère une réduction de la dimensionnalité de l'analyse en composantes principales. Nous présentons cette méthode sur des exemples et des ensembles de données synthétiques. Enfin, nous l'appliquons dans le contexte de la biologie à l'analyse d'un ensemble de données de séquençage d'ARN monocellulaire à haut débit (scRNAseq), afin d'améliorer le regroupement des cellules et de déduire les relations entre les gènes de manière non supervisée.

Pas de résumé disponible.

Pas de résumé disponible.

Les problèmes d’optimisation apparaissent naturellement pendant l’entraine-ment de modèles d’apprentissage supervises. Un exemple typique est le problème deminimisation du risque empirique (ERM), qui vise a trouver un estimateur en mini-misant le risque sur un ensemble de données. Le principal défi consiste a concevoirdes algorithmes d’optimisation efficaces permettant de traiter un grand nombre dedonnées dans des espaces de grande dimension. Dans ce cadre, les méthodes classiques d’optimisation, telles que l’algorithme de descente de gradient et sa varianteaccélérée, sont couteux en termes de calcul car elles nécessitent de passer a traverstoutes les données a chaque évaluation du gradient. Ce défaut motive le développement de la classe des algorithmes incrémentaux qui effectuent des mises a jour avecdes gradients incrémentaux. Ces algorithmes réduisent le cout de calcul par itération, entrainant une amélioration significative du temps de calcul par rapport auxméthodes classiques. Une question naturelle se pose : serait-il possible d’accélérerdavantage ces méthodes incrémentales ? Nous donnons ici une réponse positive, enintroduisant plusieurs schémas d’accélération génériques.Dans le chapitre 2, nous développons une variante proximale de l’algorithmeFinito/MISO, qui est une méthode incrémentale initialement conçue pour des problèmes lisses et fortement convexes. Nous introduisons une étape proximale dans lamise a jour de l’algorithme pour prendre en compte la pénalité de régularisation quiest potentiellement non lisse. L’algorithme obtenu admet un taux de convergencesimilaire a l’algorithme Finito/MISO original.Dans le chapitre 3, nous introduisons un schéma d’accélération générique, appele Catalyst, qui s’applique a une grande classe de méthodes d’optimisation, dansle cadre d’optimisations convexes. La caractéristique générique de notre schémapermet l’utilisateur de sélectionner leur méthode préférée la plus adaptée aux problemes. Nous montrons que en appliquant Catalyst, nous obtenons un taux deconvergence accélère. Plus important, ce taux coïncide avec le taux optimale desméthodes incrémentales a un facteur logarithmique pres dans l’analyse du pire descas. Ainsi, notre approche est non seulement générique mais aussi presque optimale du point de vue théorique. Nous montrons ensuite que l’accélération est bienprésentée en pratique, surtout pour des problèmes mal conditionnes.Dans le chapitre 4, nous présentons une seconde approche générique qui appliqueles principes Quasi-Newton pour accélérer les méthodes de premier ordre, appeléeQNing. Le schéma s’applique a la même classe de méthodes que Catalyst. En outre,il admet une simple interprétation comme une combinaison de l’algorithme L-BFGSet de la régularisation Moreau-Yosida. A notre connaissance, QNing est le premieralgorithme de type Quasi-Newton compatible avec les objectifs composites et lastructure de somme finie.Nous concluons cette thèse en proposant une extension de l’algorithme Catalyst au cas non convexe. Il s’agit d’un travail en collaboration avec Dr. CourtneyPaquette et Pr. Dmitriy Drusvyatskiy, de l’Université de Washington, et mes encadrants de thèse. Le point fort de cette approche réside dans sa capacité a s’adapterautomatiquement a la convexité. En effet, aucune information sur la convexité de lafonction n’est nécessaire avant de lancer l’algorithme. Lorsque l’objectif est convexe,l’approche proposée présente les mêmes taux de convergence que l’algorithme Catalyst convexe, entrainant une accélération. Lorsque l’objectif est non-convexe, l’algorithme converge vers les points stationnaires avec le meilleur taux de convergencepour les méthodes de premier ordre. Des résultats expérimentaux prometteurs sontobserves en appliquant notre méthode a des problèmes de factorisation de matriceparcimonieuse et a l’entrainement de modèles de réseaux de neurones.

Le livre de Mallat est la référence incontestée dans ce domaine - c'est le seul qui couvre le matériel essentiel avec autant d'ampleur et de profondeur. - Laurent Demanet, Stanford UniversityLa nouvelle édition de cet ouvrage classique présente tous les concepts, techniques et applications majeurs de la représentation clairsemée, reflétant le rôle clé que joue ce sujet dans le traitement du signal d'aujourd'hui. Le livre présente clairement les représentations standard avec les transformées de Fourier, ondelettes et temps-fréquence, ainsi que la construction de bases orthogonales avec des algorithmes rapides. Le concept central de sparsité est expliqué et appliqué à la compression du signal, à la réduction du bruit et aux problèmes inverses, tandis que les représentations éparses sont abordées dans les dictionnaires redondants, la super-résolution et les applications de détection compressive.Caractéristiques:- Equilibre entre la présentation des mathématiques et les applications au traitement du signal- Les algorithmes et les exemples numériques sont implémentés dans WaveLab, une boîte à outils MATLABNouveautés dans cette édition- Représentations de signaux épars dans les dictionnaires- Détection compressive, super-résolution et séparation de sources- Traitement d'images géométriques avec les curvelets et les bandlets- Ondelettes pour l'infographie avec levage sur les surfaces- Traitement audio temps-fréquence et débruitage- Compression d'images avec JPEG-2000- Exercices nouveaux et actualisésA Wavelet Tour of Signal Processing : The Sparse Way, Third Edition, est une ressource inestimable pour les chercheurs et les ingénieurs R&D souhaitant appliquer la théorie dans des domaines tels que le traitement des images, le traitement et la compression vidéo, la biodétection, l'imagerie médicale, la vision industrielle et l'ingénierie des communications.Stephane Mallat est professeur de mathématiques appliquées à l'École Polytechnique, Paris, France. De 1986 à 1996, il a été professeur à l'Institut Courant des sciences mathématiques de l'Université de New York et, entre 2001 et 2007, il a cofondé une société de semi-conducteurs pour le traitement des images dont il est devenu le PDG.Inclut tous les derniers développements depuis la publication du livre en 1999, y compris son application à JPEG 2000 et MPEG-4Les algorithmes et les exemples numériques sont implémentés dans Wavelab, une boîte à outils MATLABEquilibre la présentation des mathématiques avec les applications au traitement du signal.

Cet article étudie la régression des moindres carrés pénalisée par des régularisateurs convexes partiellement lisses. Cette classe de fonctions de pénalité est très large et versatile, et permet de promouvoir des solutions conformes à une certaine notion de faible complexité. En effet, de telles pénalités/régularisateurs forcent les solutions correspondantes à appartenir à un collecteur de faible dimension (le "modèle") qui reste stable lorsque la fonction de pénalité subit de petites perturbations. Une telle propriété de sensibilité est cruciale pour rendre le modèle (manifold) sous-jacent de faible complexité robuste au petit bruit. Dans un cadre déterministe, nous montrons qu'une "condition irreprésentable" généralisée implique une sélection de modèle stable sous de petites perturbations de bruit dans les observations et la matrice de conception, lorsque le paramètre de régularisation est accordé proportionnellement au niveau de bruit. Nous prouvons également que cette condition est presque nécessaire pour la récupération stable du modèle.nous nous tournons ensuite vers le cadre aléatoire où la matrice de conception et le bruit sont aléatoires, et le nombre d'observations augmente. Nous montrons que sous notre "condition irreprésentable" généralisée, et une mise à l'échelle appropriée du paramètre de régularisation, l'estimateur régularisé est cohérent avec le modèle. En d'autres termes, avec une probabilité tendant vers un lorsque le nombre de mesures tend vers l'infini, l'estimateur régularisé appartient au bon collecteur de modèle de basse dimension.Ce travail unifie et généralise un grand nombre de publications, où la cohérence du modèle était connue pour être valable, par exemple pour les régularisateurs Lasso, Lasso de groupe, variation totale (Lasso fusionné) et norme nucléaire/trace.Nous montrons que sous les conditions déterministes de sélection du modèle, l'algorithme de séparation proximale avant-arrière utilisé pour résoudre le problème de régression des moindres carrés pénalisés, est garanti d'identifier le collecteur du modèle après un nombre fini d'itérations. Enfin, nous détaillons comment nos résultats s'étendent de la perte quadratique à une fonction de perte arbitraire lisse et strictement convexe. Nous illustrons l'utilité de nos résultats sur le problème de la récupération de matrices de bas rang à partir de mesures aléatoires en utilisant la minimisation de la norme nucléaire.

Nous proposons une représentation éparse des formes planes en 2D par la composition de fonctions de déformation, appelées formlets, localisées dans l'échelle et l'espace. Chaque formlet soumet l'espace 2D dans lequel la forme est intégrée à une déformation radiale isotrope localisée. En contraignant ces transfor- mations de déformation localisées à être des difféomorphismes, la topologie de la forme est préservée, et l'ensemble des courbes simples fermées est fermé sous toute séquence de ces déformations. Un modèle génératif basé sur une composition de formlets appliquée à une forme embryonnaire, par exemple une ellipse, présente l'avantage de ne synthétiser que les formes qui pourraient correspondre aux limites d'objets physiques. Pour calculer l'ensemble des formlets qui représentent une frontière donnée, nous démontrons un algorithme gourmand de poursuite de formlets grossiers à fins qui sert de généralisation non-commutative de la poursuite de l'appariement pour les approximations éparses. Nous évaluons notre méthode en poursuivant des formes partiellement occultées, en comparant les performances à celles d'un cadre de codage de formes clairsemées basé sur les contours.