Briser la Malédiction de la Dimensionnalité avec des Réseaux Neuraux Convexes

Nous considérons des réseaux neuronaux avec une seule couche cachée et des fonctions d'activation homogènes non décroissantes comme les unités linéaires rectifiées. En laissant croître sans limite le nombre d'unités cachées et en utilisant des outils de régularisation non-euclidienne classiques sur les poids de sortie, nous fournissons une analyse théorique détaillée de leur performance de généralisation, avec une étude des erreurs d'approximation et d'estimation. Nous montrons en particulier qu'ils sont adaptatifs aux structures linéaires sous-jacentes inconnues, telles que la dépendance de la projection des variables d'entrée sur un sous-espace de faible dimension. De plus, lors de l'utilisation de normes induisant la parcimonie sur les poids d'entrée, nous montrons qu'une sélection de variables non linéaires en haute dimension peut être réalisée, sans aucune hypothèse forte concernant les données et avec un nombre total de variables potentiellement exponentiel par rapport au nombre d'observations. En outre, nous fournissons une simple interprétation géométrique au problème non convexe de l'ajout d'une nouvelle unité, qui est l'élément computationnel potentiellement difficile dans le cadre de l'apprentissage à partir de continuellement nombreuses fonctions de base. Nous donnons des conditions simples pour que des relaxations convexes atteignent les mêmes bornes d'erreur de généralisation, même lorsque des approximations à facteur constant ne peuvent pas être trouvées (par exemple, parce que c'est NP-difficile comme pour la fonction d'activation zéro-homogène). Nous n'avons pas pu trouver de relaxations convexes suffisamment fortes et laissons ouverte l'existence ou non-existence d'algorithmes en temps polynomial.