FLAMMARION Nicolas

Nous considérons la minimisation d'une fonction définie sur un collecteur riemannien $\mathcal{M}$ accessible uniquement par des estimations non biaisées de ses gradients. Nous développons un cadre géométrique pour transformer une séquence d'itérations à convergence lente générée par la descente de gradient stochastique (SGD) sur $\mathcal{M}$ en une séquence d'itérations moyennées avec un taux de convergence robuste et rapide de $O(1/n)$. Nous présentons ensuite une application de notre cadre à des problèmes géodésiquement fortement convexes (et éventuellement non convexes euclidiens). Enfin, nous démontrons comment ces idées s'appliquent au cas de l'ACP à k$ en continu, où nous montrons comment accélérer le taux lent de la méthode de puissance aléatoire (sans exiger la connaissance de l'eigengap) en un algorithme robuste atteignant le taux de convergence optimal.

Nous considérons l'optimisation d'une fonction objectif quadratique dont les gradients ne sont accessibles qu'à travers un oracle stochastique qui renvoie le gradient à tout point donné plus une erreur aléatoire de variance finie de moyenne nulle. Nous présentons le premier algorithme qui atteint conjointement les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, à la fois en termes d'oubli des conditions initiales en O(1/n 2), et en termes de dépendance au bruit et à la dimension d du problème, en O(d/n). Notre nouvel algorithme est basé sur la descente de gradient régularisée accélérée moyenne, et peut également être analysé par des hypothèses plus fines sur les conditions initiales et la matrice hessienne, conduisant à des quantités sans dimension qui peuvent encore être petites alors que les termes " optimaux " ci-dessus sont grands. Afin de caractériser l'étanchéité de ces nouvelles limites, nous considérons une application à la régression non paramétrique et utilisons les limites inférieures connues de la performance statistique (sans limites de calcul), qui correspondent à nos limites obtenues à partir d'un seul passage sur les données et montrent ainsi l'optimalité de notre algorithme dans une grande variété de compromis particuliers entre le biais et la variance.

De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficace.

La mise en grappes de données à haute dimension nécessite souvent une certaine forme de réduction de la dimensionnalité, où les variables mises en grappes sont séparées des variables " bruyantes ". Ce problème consiste à trouver une projection à faible dimension des données qui sont bien groupées. Cela donne une projection unidimensionnelle dans la situation la plus simple avec deux clusters, et s'étend naturellement à un scénario multi-label pour plus de deux clusters. Dans cet article, (a) nous montrons d'abord que cette formulation conjointe de clustering et de réduction de dimension est équivalente aux cadres de clustering discriminatif proposés précédemment, ce qui conduit à des relaxations convexes du problème. (b) Nous proposons une nouvelle extension éparse, qui reste une relaxation convexe et permet l'estimation dans des dimensions supérieures. (c) Nous proposons une extension naturelle pour le scénario multi-labels. (d) nous fournissons une nouvelle analyse théorique de la performance de ces formulations avec un modèle probabiliste simple, conduisant à des mises à l'échelle de la forme d = O(√ n) pour le cas affine invariant et d = O(n) pour le cas clairsemé, où n est le nombre d'exemples et d la dimension ambiante. et enfin, (e) nous proposons un algorithme itératif efficace avec une complexité de temps d'exécution proportionnelle à O(nd 2), améliorant les algorithmes précédents qui avaient une complexité quadratique dans le nombre d'exemples.

Nous considérons l'optimisation d'une fonction objectif quadratique dont les gradients ne sont accessibles qu'à travers un oracle stochastique qui renvoie le gradient à tout point donné plus une erreur aléatoire de variance finie de moyenne nulle. Nous présentons le premier algorithme qui atteint conjointement les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, à la fois en termes d'oubli des conditions initiales en O(1/n 2), et en termes de dépendance au bruit et à la dimension d du problème, en O(d/n). Notre nouvel algorithme est basé sur la descente de gradient régularisée accélérée moyenne, et peut également être analysé par des hypothèses plus fines sur les conditions initiales et la matrice hessienne, conduisant à des quantités sans dimension qui peuvent encore être petites alors que les termes " optimaux " ci-dessus sont grands. Afin de caractériser l'étanchéité de ces nouvelles limites, nous considérons une application à la régression non paramétrique et utilisons les limites inférieures connues de la performance statistique (sans limites de calcul), qui correspondent à nos limites obtenues à partir d'un seul passage sur les données et montrent ainsi l'optimalité de notre algorithme dans une grande variété de compromis particuliers entre le biais et la variance.

De nombreux problèmes d'apprentissage automatique sont naturellement présentés comme la minimisation d'une fonction lisse définie dans un espace euclidien. Pour l'apprentissage supervisé, cela inclut la régression des moindres carrés et la régression logistique. Alors que les petits problèmes sont résolus efficacement par les algorithmes d'optimisation classiques, les problèmes à grande échelle sont généralement résolus avec des techniques de premier ordre basées sur la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans la première partie, nous nous intéressons à sa minimisation lorsque ses gradients ne sont accessibles que par un oracle stochastique. Dans la seconde partie, nous considérons deux applications de la perte quadratique en apprentissage automatique : le clustering et l'estimation avec des contraintes de forme. Dans la première contribution principale, nous avons fourni un cadre unifié pour l'optimisation des fonctions quadratiques non fortement convexes, qui englobe la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui présente le comportement positif de la moyenne et de l'accélération. La deuxième contribution principale vise à obtenir les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, tant en termes de dépendance au bruit du problème que d'oubli des conditions initiales. Notre nouvel algorithme repose sur la descente de gradient accélérée et moyennée. La troisième contribution principale traite de la minimisation de fonctions objectives composites composées de l'espérance de fonctions quadratiques et d'une fonction convexe. Nous étendons les résultats précédents sur la régression des moindres carrés à tout régularisateur et à toute géométrie représentée par une divergence de Bregman. Comme quatrième contribution, nous considérons le cadre du clustering discriminatif. Nous proposons sa première analyse théorique, une nouvelle extension sparse, une extension naturelle pour le scénario multi-label et un algorithme itératif efficace avec une meilleure complexité en temps de fonctionnement que les méthodes existantes. La cinquième contribution principale traite du problème de la sériation. Nous proposons une approche statistique de ce problème où la matrice est observée avec du bruit et étudions le taux d'estimation minimax correspondant. Nous suggérons également un estimateur efficace en termes de calcul dont les performances sont étudiées à la fois théoriquement et expérimentalement.

Étant donné une matrice, le problème de la sériation consiste à permuter ses lignes de manière à ce que toutes ses colonnes aient la même forme, par exemple, elles sont monotones croissantes. Nous proposons une approche statistique de ce problème où la matrice d'intérêt est observée avec du bruit et étudions le taux d'estimation minimax correspondant des matrices. Plus précisément, lorsque les colonnes sont soit unimodales soit monotones, nous montrons que l'estimateur des moindres carrés est optimal jusqu'à des facteurs logarithmiques et s'adapte aux matrices ayant une certaine structure naturelle. Enfin, nous proposons un estimateur efficace en termes de calcul dans le cas monotone et étudions ses performances à la fois théoriquement et expérimentalement. Notre travail se situe à l'intersection de l'estimation sous contrainte de forme et des travaux récents qui impliquent l'apprentissage par permutation, comme le débruitage et le classement de graphes.

Nous montrons que la descente de gradient accélérée, la descente de gradient moyennée et la méthode de la boule lourde pour les problèmes non fortement convexes peuvent être reformulées comme des algorithmes d'équation aux différences du second ordre à paramètres constants, où la stabilité du système est équivalente à la convergence à un taux O(1/n 2), où n est le nombre d'itérations. Nous fournissons une analyse détaillée des valeurs propres du système dynamique linéaire correspondant, montrant divers comportements oscillatoires et non-oscillatoires, ainsi qu'un résultat de stabilité net avec des constantes explicites. Nous considérons également la situation où des gradients bruyants sont disponibles, où nous étendons notre résultat de convergence général, ce qui suggère un algorithme alternatif (c'est-à-dire avec différentes tailles de pas) qui présente les bons aspects de la moyenne et de l'accélération.