DIEULEVEUT Aymeric

Les pas cycliques sont de plus en plus populaires dans l'optimisation des problèmes d'apprentissage profond. Motivés par des observations récentes sur les écarts spectraux des Hessiens dans l'apprentissage automatique, nous montrons que ces pas cycliques offrent un moyen simple de les exploiter. Plus précisément, nous développons une analyse du taux de convergence pour les objectifs quadratiques qui fournit des paramètres optimaux et montre que les taux d'apprentissage cycliques peuvent améliorer les limites de complexité inférieures traditionnelles. Nous proposons en outre une approche systématique pour concevoir des méthodes optimales de premier ordre pour la minimisation quadratique avec une structure spectrale donnée. Enfin, nous fournissons une analyse du taux de convergence locale au-delà de la minimisation quadratique pour les méthodes proposées et illustrons nos résultats par des benchmarks sur des problèmes de moindres carrés et de régression logistique.

L'algorithme Expectation Maximization (EM) est l'algorithme par défaut pour l'inférence dans les modèles à variables latentes. Comme dans tout autre domaine de l'apprentissage automatique, les applications des modèles à variables latentes à de très grands ensembles de données rendent obligatoire l'utilisation d'architectures parallèles et distribuées avancées. Cet article présente FedEM, qui est la première extension de l'algorithme EM au contexte de l'apprentissage fédéré. FedEM est une nouvelle méthode efficace de communication, qui gère la participation partielle des dispositifs locaux et qui est robuste aux distributions hétérogènes des ensembles de données. Pour alléger le goulot d'étranglement de la communication, FedEM compresse les statistiques suffisantes des données complètes définies de manière appropriée. Nous développons et analysons également une extension de FedEM pour incorporer un schéma de réduction de la variance. Dans tous les cas, nous dérivons des limites de complexité en temps fini pour des problèmes lisses non convexes. Des résultats numériques sont présentés pour étayer nos conclusions théoriques, ainsi qu'une application à l'imputation fédérée des valeurs manquantes pour le suivi de la biodiversité.

L'incomplétude des données à grande échelle est un problème majeur. Nous proposons un algorithme de gradient stochastique moyenné traitant les valeurs manquantes dans les modèles linéaires. Cette approche a le mérite de ne nécessiter aucune modélisation de la distribution des données et de tenir compte de la proportion hétérogène de valeurs manquantes. Nous prouvons que cet algorithme atteint un taux de convergence de O(1 n) à l'itération n, comme en l'absence de valeurs manquantes. Nous montrons le comportement de convergence et la pertinence de l'algorithme non seulement sur des données synthétiques mais aussi sur des ensembles de données réelles, y compris celles collectées dans des registres médicaux.

Les séries temporelles constituent un type de données difficile pour les algorithmes d'apprentissage automatique, en raison de leurs longueurs très variables et de leur étiquetage clairsemé dans la pratique. Dans cet article, nous nous attaquons à ce défi en proposant une méthode non supervisée d'apprentissage d'intégrations universelles de séries temporelles. Contrairement aux travaux précédents, cette méthode est évolutive par rapport à leur longueur et nous démontrons la qualité, la transférabilité et la praticabilité des représentations apprises par des expériences et des comparaisons approfondies. À cette fin, nous combinons un encodeur basé sur des convolutions dilatées causales avec une nouvelle perte de triplet utilisant un échantillonnage négatif basé sur le temps, obtenant des représentations polyvalentes pour des séries temporelles de longueur variable et multivariées.

Pas de résumé disponible.

Nous considérons la minimisation d'une fonction objective en ayant accès à des estimations non biaisées de son gradient par la descente de gradient stochastique (SGD) avec une taille de pas constante. Bien que l'analyse détaillée n'ait été effectuée que pour des fonctions quadratiques, nous fournissons une expansion asymptotique explicite des moments des itérations SGD moyennées qui souligne la dépendance aux conditions initiales, l'effet du bruit et de la taille du pas, ainsi que l'absence de convergence dans le cas général (non quadratique). Pour cette analyse, nous introduisons des outils issus de la théorie des chaînes de Markov dans l'analyse du gradient stochastique. Nous montrons ensuite que l'extrapolation de Richardson-Romberg peut être utilisée pour se rapprocher de l'optimum global et nous montrons les améliorations empiriques du nouveau schéma d'extrapolation.

L'objectif de l'apprentissage automatique supervisé est d'inférer des relations entre un phénomène que l'on cherche à prédire et des variables "explicatives". À cette fin, de multiples occurrences du phénomène sont observées, à partir desquelles une règle de prédiction est construite. Les deux dernières décennies ont vu l'apparition de très grands ensembles de données, tant en termes de nombre d'observations (par exemple, en analyse d'images) qu'en termes de nombre de variables explicatives (par exemple, en génétique). Cela a soulevé deux défis : premièrement, éviter l'écueil de l'ajustement excessif, en particulier lorsque le nombre de variables explicatives est beaucoup plus élevé que le nombre d'observations, et deuxièmement, faire face aux contraintes de calcul, par exemple lorsque la simple résolution d'un système linéaire devient une difficulté en soi. Les algorithmes qui prennent leurs racines dans les méthodes d'approximation stochastiques s'attaquent à ces deux difficultés simultanément : ces méthodes stochastiques réduisent considérablement le coût de calcul, sans dégrader la qualité de la règle de prédiction proposée, et elles peuvent naturellement éviter le surajustement. En conséquence, le cœur de cette thèse sera l'étude des méthodes de gradient stochastiques. Les méthodes paramétriques populaires donnent des prédicteurs qui sont des fonctions linéaires d'un ensemble de variables explicatives. Cependant, elles aboutissent souvent à une approximation imprécise de la structure statistique sous-jacente. Dans le cadre non-paramétrique, qui est primordial dans cette thèse, cette restriction est levée. La classe de fonctions à partir de laquelle le prédicteur est proposé dépend des observations. En pratique, ces méthodes ont des objectifs multiples, et sont essentielles pour l'apprentissage avec des données non vectorielles, qui peuvent être mappées sur un vecteur dans un espace fonctionnel en utilisant un noyau défini positif. Cela permet d'utiliser des algorithmes conçus pour des données vectorielles, mais nécessite de faire l'analyse dans l'espace associé non paramétrique : l'espace de Hilbert à noyau reproducteur. De plus, l'analyse de la régression non-paramétrique apporte également un éclairage sur le cadre paramétrique lorsque le nombre de prédicteurs est beaucoup plus grand que le nombre d'observations. La première contribution de cette thèse est de fournir une analyse détaillée de l'approximation stochastique dans le cadre non-paramétrique, précisément dans les espaces de Hilbert à noyau reproducteur. Cette analyse prouve des taux de convergence optimaux pour l'algorithme de descente de gradient stochastique moyenné. Comme nous prenons soin d'utiliser des hypothèses minimales, elle s'applique à de nombreuses situations, et couvre à la fois les situations dans lesquelles le nombre d'observations est connu a priori, et les situations dans lesquelles l'algorithme d'apprentissage fonctionne en ligne. La deuxième contribution est un algorithme basé sur l'accélération, qui converge à une vitesse optimale, tant du point de vue de l'optimisation que du point de vue statistique. Dans le cadre non-paramétrique, cela peut améliorer le taux de convergence jusqu'à l'optimalité, même dans des régimes particuliers pour lesquels le premier algorithme reste sous-optimal. Enfin, la troisième contribution de la thèse consiste en une extension du cadre au-delà de la perte des moindres carrés. L'algorithme de descente de gradient stochastique est analysé comme une chaîne de Markov. Ce point de vue conduit à une interprétation intuitive et perspicace, qui souligne les différences entre le cadre quadratique et le cadre plus général. Une méthode simple permettant de prouver l'amélioration de la convergence est ensuite proposée.

Le but de l’apprentissage supervisé est d’inférer des relations entre un phénomène que l’on souhaite prédire et des variables « explicatives ». À cette fin, on dispose d’observations de multiples réalisations du phénomène, à partir desquelles on propose une règle de prédiction. L’émergence récente de sources de données à très grande échelle, tant par le nombre d’observations effectuées (en analyse d’image, par exemple) que par le grand nombre de variables explicatives (en génétique), a fait émerger deux difficultés : d’une part, il devient difficile d’éviter l’écueil du sur-apprentissage lorsque le nombre de variables explicatives est très supérieur au nombre d’observations. d’autre part, l’aspect algorithmique devient déterminant, car la seule résolution d’un système linéaire dans les espaces en jeupeut devenir une difficulté majeure. Des algorithmes issus des méthodes d’approximation stochastique proposent uneréponse simultanée à ces deux difficultés : l’utilisation d’une méthode stochastique réduit drastiquement le coût algorithmique, sans dégrader la qualité de la règle de prédiction proposée, en évitant naturellement le sur-apprentissage. En particulier, le cœur de cette thèse portera sur les méthodes de gradient stochastique. Les très populaires méthodes paramétriques proposent comme prédictions des fonctions linéaires d’un ensemble choisi de variables explicatives. Cependant, ces méthodes aboutissent souvent à une approximation imprécise de la structure statistique sous-jacente. Dans le cadre non-paramétrique, qui est un des thèmes centraux de cette thèse, la restriction aux prédicteurs linéaires est levée. La classe de fonctions dans laquelle le prédicteur est construit dépend elle-même des observations. En pratique, les méthodes non-paramétriques sont cruciales pour diverses applications, en particulier pour l’analyse de données non vectorielles, qui peuvent être associées à un vecteur dans un espace fonctionnel via l’utilisation d’un noyau défini positif. Cela autorise l’utilisation d’algorithmes associés à des données vectorielles, mais exige une compréhension de ces algorithmes dans l’espace non-paramétrique associé : l’espace à noyau reproduisant. Par ailleurs, l’analyse de l’estimation non-paramétrique fournit également un éclairage révélateur sur le cadre paramétrique, lorsque le nombre de prédicteurs surpasse largement le nombre d’observations. La première contribution de cette thèse consiste en une analyse détaillée de l’approximation stochastique dans le cadre non-paramétrique, en particulier dans le cadre des espaces à noyaux reproduisants. Cette analyse permet d’obtenir des taux de convergence optimaux pour l’algorithme de descente de gradient stochastique moyennée. L’analyse proposée s’applique à de nombreux cadres, et une attention particulière est portée à l’utilisation d’hypothèses minimales, ainsi qu’à l’étude des cadres où le nombre d’observations est connu à l’avance, ou peut évoluer. La seconde contribution est de proposer un algorithme, basé sur un principe d’accélération, qui converge à une vitesse optimale, tant du point de vue de l’optimisation que du point de vue statistique. Cela permet, dans le cadre non-paramétrique, d’améliorer la convergence jusqu’au taux optimal, dans certains régimes pour lesquels le premier algorithme analysé restait sous-optimal. Enfin, la troisième contribution de la thèse consiste en l’extension du cadre étudié au delà de la perte des moindres carrés : l’algorithme de descente de gradient stochastiqueest analysé comme une chaine de Markov. Cette approche résulte en une interprétation intuitive, et souligne les différences entre le cadre quadratique et le cadre général. Une méthode simple permettant d’améliorer substantiellement la convergence est également proposée.

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.

Nous considérons le problème de la régression des moindres carrés à conception aléatoire dans le cadre de l'espace de Hilbert à noyau reproducteur (RKHS). Étant donné un flux de données d'entrée/sortie indépendantes et identiquement distribuées, nous cherchons à apprendre une fonction de régression dans un RKHS $\mathcal{H}$, même si le prédicteur optimal (c'est-à-dire l'espérance conditionnelle) n'est pas dans $\mathcal{H}$. Dans un cadre d'approximation stochastique où l'estimateur est mis à jour après chaque observation, nous montrons que l'algorithme des moindres carrés moyens non régularisés (une forme de gradient stochastique), compte tenu d'une taille de pas suffisamment grande, atteint des taux de convergence optimaux pour une variété de régimes pour les lissages de la fonction de prédiction optimale et des fonctions dans $\mathcal{H}$.