Thèse une Théorie de la Complexité Robuste pour les Calculs Universels par les Réseaux de Neurones H/F - Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique École doctorale : Sciences et Technologies de l'Information et de la Communication Laboratoire de recherche : Laboratoire Interdisciplinaire des Sciences du Numérique Direction de la thèse : Johanne COHEN Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-12T23:59:59 Les modèles d'apprentissage profond ont révolutionné l'apprentissage automatique et possèdent aujourd'hui une liste impressionnante de succès. Cependant, à ce jour, il manque une véritable théorie de la complexité robuste et associée à ces modèles. Voir par exemple [3] pour un cours récent présentant l'état de l'art actuel.

Une raison fondamentale de cette absence de théorie est que les modèles impliqués ne sont pas des modèles classiques de calcul sur le discret, mais sur les nombres réels. La théorie de la complexité et de la calculabilité pour les modèles continus est loin d'être aussi claire que celle pour les modèles discrets.

Par exemple, un des résultats fondamentaux les plus cités de la théorie des réseaux de neurones est qu'ils sont des approximants universels : pour toute fonction continue, tout domaine compact et toute précision , il existe un réseau de neurones dont la distance à la fonction sur ce domaine est au plus . Mathématiquement, cela signifie que la classe des fonctions réalisables par des réseaux de neurones est dense dans l'ensemble des fonctions continues sur des domaines compacts. Ce résultat tient sous des hypothèses minimales (une seule couche cachée et une fonction d'activation non polynomiale suffisent [4, 6]). Cependant, il n'apporte aucune information sur la complexité de l'approximation.

L'article A Universal Uniform Approximation Theorem for Neural Networks [2] a établi qu'un seul réseau récurrent fixe à activation ReLU peut approximer uniformément toute fonction continue calculable tout en préservant une complexité en temps polynomial. Ce résultat relie la complexité computationnelle classique aux modèles continus de calcul et aux architectures neuronales. Il établit un lien entre la théorie des réseaux de neurones et la théorie classique de la calculabilité et de la complexité.

Des travaux complémentaires de Bournez, Dardhilac et Cohen [1] ont développé un cadre théorique pour la complexité des calculs analogiques et en temps continu, fournissant des outils pour analyser la puissance expressive et computationnelle des systèmes dynamiques et des modèles neuronaux. L'idée est de considérer des modèles où la décision n'est pas nécessairement exacte mais robuste aux perturbations des entrées, dans l'esprit de la -décidabilité [5]. Ensemble, ces travaux ouvrent la voie à une théorie unifiée, robuste et mathématiquement fondée de la complexité pour la computation neuronale, englobant les paradigmes discrets et en temps continu.

Au-delà de l'approximation de fonctions statiques, une ligne majeure de recherche consiste à étudier comment les architectures neuronales peuvent modéliser des systèmes dynamiques en temps continu. En particulier, les équations différentielles neuronales (Neural ODEs) établissent un pont entre l'apprentissage profond et les modèles de calcul en temps continu sur les réels. Des travaux récents, tels que [?], approfondissent cette connexion en proposant des approches permettant d'apprendre des systèmes dynamiques sans solveur d'EDO interne, améliorant ainsi l'interprétabilité et la stabilité numérique. Le stage s'inscrit dans le développement d'une théorie de la complexité robuste pour le calcul neuronal, reliant les modèles continus (réseaux de neurones, équations différentielles neuronales) et les modèles discrets classiques de la théorie de la complexité.
Il s'agit de comprendre la puissance de calcul et la robustesse des réseaux de neurones au-delà des activations ReLU, en s'appuyant sur les cadres de calculabilité sur les réels et de -décidabilité. Il vise à étendre les résultats au-delà de la fonction d'activation ReLU, en explorant des classes plus larges d'activations analytiques et polynomiales, la robustesse aux perturbations et l'émergence de hiérarchies de complexité neuronale. Le stage abordera plusieurs axes de recherche complémentaires :

Approximation universelle robuste au-delà de ReLU
Étendre les résultats d'approximation universelle des activations linéaires par morceaux (ReLU) à des familles d'activations plus générales telles que les fonctions sigmoïdes, polynomiales ou analytiques. Étudier comment la précision limitée, les poids rationnels ou les perturbations affectent la complexité du calcul, et formaliser une notion de calculabilité robuste pour les réseaux de neurones.

Décision approchée (-décidabilité) pour la computation neuronale
S'appuyer sur les modèles de calcul analogique et basés sur les EDO inspirés du cadre CCC 2024 [1]. Établir des correspondances entre robustesse / stabilité numérique, flots neuronaux en temps continu et architectures discrètes ; relier le temps d'intégration des systèmes d'EDO à la profondeur ou à la taille des réseaux, et explorer les implications en complexité.

Hiérarchies de complexité neuronale
Définir et comparer les classes de fonctions calculables par des réseaux neuronaux sous des contraintes de ressources polynomiales ou exponentielles. Étudier leurs relations avec les classes de complexité classiques et avec les mesures de complexité de type circuits, comme les mesures de type Kolmogorov KT(f).

Gout pour l'informatique théorique