Optimisation pour l'apprentissage automatique : complexité moyenne en grande dimension et la dynamique exacte

Les algorithmes jouent un rôle essentiel dans l’apprentissage automatique et ont connu un succès empirique généralisé sur des problèmes d’apprentissage en grande dimension (par exemple, le nombre de caractéristiques et d’échantillons est important). Malgré leur popularité, il existe un écart entre les performances réelles et les limites théoriques connues. En général, la théorie de la complexité des algorithmes d’apprentissage se concentre sur l’analyse du pire des cas, qui garantit la convergence de toutes les entrées sous des hypothèses générales (convexité et régularité) sur la fonction objectif. La grande dimension n’est souvent pas explicitement imposée, ce qui entraine plus de possibilités pour les entrées dans un algorithme, de sorte que le cas le plus défavorable peut-être très différent du cas typique.

Le but de la complexité en moyenne est de calculer l’espérance de la complexité d’un algorithme par des méthodes probabilistes. Par rapport à l’analyse du cas le plus défavorable, elle est plus représentative du comportement typique, mais cette méthode reste largement inexplorée en optimisation. Un défi consiste donc à trouver une distribution de probabilité sur l’entrée (ensemble de données) qui modèle des données réelles et se prête à l’analyse. Ce projet aborde une série de questions de recherche concernant la complexité moyenne des méthodes du premier ordre en grande dimension. Le projet cherche à répondre à la question suivante.

Développez un cadre général pour la complexité moyenne des algorithmes d’apprentissage et analysez leur dynamique exacte pour mieux comprendre le pas de progression et les propriétés de convergence.

Le projet comporte deux parties. Premièrement, la chercheuse principale explore les questions concernant la dynamique des algorithmes d’optimisation stochastique en grande dimension pour la méthode des moindres carrés aléatoires. En particulier, la chercheuse principale prévoit d’étudier les relations entre la complexité moyenne, les stratégies de sélection des paramètres de pas et de quantité de mouvement, la taille des lots et les hypothèses de modélisation sur l’ensemble de données et les cibles. En effet, une grande capacité de calcul est gaspillé à essayer de trouver des tailles de pas qui donner de bons optimiseurs dans un temps raisonnable. L’analyse des cas moyens permet de sélectionner des paramètres pour obtenir des algorithme efficace en grande dimension. Deuxièmement, pour divers problèmes de minimisation (par exemple, les modèles linéaires généralisés (GLM), les fonctions objectives non lisses), il n’y a pas de modèles fiable pour décrire à la fois le comportement de données réelles en tant qu’entrées dans les fonctions objectives et les matrices hessiennes. Le spectre de la matrice hessienne permet de décrire la géométrie des fonctions objectives complexes. La chercheuse principale propose d’analyser la complexité en moyenne d’algorithmes d’optimisation plus compliqué que les problèmes quadratiques en utilisant la théorie des matrices aléatoires pour décrire ce spectre.