📊 statistics

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

Cet article établit une dichotomie d'espace de fonctions démontrant que le Noyau Tangent Neural souffre d'une sous-optimalité exponentielle par rapport aux réseaux de neurones à largeur finie sur les tâches compositionnelles, un écart piloté par le décalage entre le biais de lissage du noyau et la complexité architecturale de la cible plutôt que par une limitation générique noyau-versus-réseau.

Auteurs originaux : Arkaprabha Ganguli, Emil Constantinescu

Publié 2026-07-08

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Arkaprabha Ganguli, Emil Constantinescu

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

L'idée générale : Pourquoi l'apprentissage « paresseux » échoue à construire des choses complexes

Imaginez que vous essayiez d'apprendre à un ordinateur à reconnaître des motifs. Pendant longtemps, les chercheurs ont utilisé un outil appelé le Noyau Tangent Neural (NTK - Neural Tangent Kernel) pour prédire la capacité d'un réseau de neurones à apprendre. Considérez le NTK comme un enseignant « paresseux ». Cet enseignant est très doué pour lisser les aspérités et apprendre des courbes douces, mais il refuse de changer d'avis ou d'apprendre de nouvelles astuces. Il se contente de s'en tenir à une façon très rigide et préétablie de voir le monde.

L'article pose une question simple : Quand cet enseignant « paresseux » échoue-t-il, et pourquoi ?

Les auteurs ont découvert que l'enseignant paresseux échoue de manière spectaculaire lorsque la tâche implique de la composition — c'est-à-dire construire quelque chose de complexe en empilant des couches simples les unes sur les autres (comme une poupée russe ou une recette comportant de nombreuses étapes). Dans ces cas, un enseignant « riche » (un réseau de neurones standard qui apprend réellement et modifie ses poids) est exponentiellement meilleur que l'enseignant paresseux.

Les deux façons de mesurer la difficulté

Pour expliquer cela, les auteurs examinent une fonction cible (le motif que l'ordinateur doit apprendre) à travers deux prismes différents :

Le prisme de la « Douceur » (Complexité de Fourier) :
Imaginez que la cible soit une note de musique. Si la note est un bourdonnement grave et doux, elle est facile à décrire. Si c'est un cri strident et saccadé qui vibre des milliers de fois par seconde, elle est « complexe » en termes de douceur.
- La vision du NTK : L'enseignant paresseux déteste les sons stridents et rapides. Pour apprendre un cri haute fréquence, le NTK a besoin d'une quantité massive de données (échantillons) pour le comprendre. Il traite chaque oscillation comme un obstacle énorme.
Le prisme « Architectural » (Complexité Architecturale) :
Maintenant, imaginez que vous vouliez construire une machine capable de produire ce même cri strident.
- La vision du Réseau : Un réseau de neurones standard est comme un maître constructeur. Même si le son est un cri fou et rapide, le constructeur peut le créer en empilant simplement quelques engrenages simples (couches). Le « coût » de construction est faible, même si le résultat semble chaotique.

Le Conflit : L'article montre que pour certaines tâches, le coût de la « Douceur » est astronomique, mais le coût « Architectural » est minuscule. L'enseignant paresseux (NTK) voit le coût astronomique et abandonne, tandis que le constructeur intelligent (réseau de neurones) voit le coût minuscule et construit facilement.

L'exemple phare : L'onde en « Dents de scie »

Les auteurs utilisent une forme spécifique appelée Dents de scie pour prouver leur point. Imaginez une onde triangulaire qui monte et descend.

Profondeur 1 : Un triangle. Facile.
Profondeur 2 : Deux triangles à l'intérieur d'un autre.
Profondeur 10 : Une onde qui zigzague de haut en bas des milliers de fois.

Le Piège :

Pour le Réseau : Vous pouvez construire cette onde folle et zigzagante en empilant seulement 10 couches simples. C'est une construction peu coûteuse et efficace.
Pour le NTK : Pour l'enseignant paresseux, cette onde semble avoir une fréquence de $2^{10}$ (plus de 1 000). Comme le NTK est biaisé vers la douceur, il pense que c'est incroyablement difficile.

Le Résultat :
L'article prouve que pour apprendre cette dent de scie à 10 couches :

Le Réseau a besoin d'un nombre gérable d'exemples (croissance polynomiale).
Le NTK a besoin d'un nombre d'exemples qui croît de manière exponentielle (comme $4^{10}$ ).
En langage courant : Lorsque la profondeur atteint seulement 12, l'enseignant paresseux aurait besoin 10 millions de fois plus de données que le constructeur intelligent pour obtenir le même résultat.

Le régime « Paresseux » vs « Riche »

L'article distingue deux manières dont les réseaux de neurones apprennent :

Le Régime Paresseux (NTK) : Le réseau est si large et entraîné si doucement que ses paramètres internes bougent à peine. Il agit comme une formule mathématique fixe (un noyau). Il est excellent pour les choses lisses et simples, mais terrible pour les choses complexes et structurées.
Le Régime Riche (Entraînement Standard) : Le réseau modifie réellement ses poids internes. Il apprend des caractéristiques (features). Cela lui permet de construire des structures complexes efficacement, même si elles paraissent désordonnées.

Ce que les expériences ont montré

Les auteurs ne se sont pas contentés de faire des mathématiques ; ils ont mené des expériences pour confirmer leur théorie :

Cibles Lisses : Lorsqu'ils ont donné à l'ordinateur une onde simple et douce (comme une onde sinusoïdale légère), l'enseignant paresseux (NTK) et le constructeur intelligent ont performé de manière presque identique. Le NTK est efficace ici.
Cibles Complexes (Parité) : Ils ont testé un problème de « parité creuse » (un puzzle logique impliquant la multiplication de nombres spécifiques).
- Le NTK était bloqué au bas de l'échelle, devinant au hasard, peu importe la quantité de données fournie.
- Le Réseau de Neurones a appris le motif rapidement, battant le NTK par un facteur de 10 000 à 1 000 000.

La Conclusion

L'article conclut que l'écart entre les réseaux de neurones et les méthodes à noyaux n'est pas seulement une question de « noyaux contre réseaux ». Il s'agit d'un décalage d'outils.

Si votre problème est lisse et simple, le noyau « paresseux » est un outil excellent et efficace.
Si votre problème est construit à partir de couches de composition (comme des hiérarchies profondes ou une logique complexe), l'outil « paresseux » est le mauvais instrument. Il voit une montagne de difficulté là où un constructeur intelligent voit un simple escalier.

La « sous-optimalité exponentielle » mentionnée dans le titre signifie simplement que pour ces types de problèmes complexes et structurés, utiliser l'approche du noyau paresseux n'est pas seulement légèrement moins bon ; c'est catastrophiquement inefficace par rapport au fait de laisser le réseau réellement apprendre.

Résumé Technique : Une dichotomie d'espaces de fonctions pour l'apprentissage compositionnel

Énoncé du Problème
Une observation empirique persistante dans l'apprentissage profond est que les réseaux de neurones entraînés surpassent systématiquement les limites de leur noyau tangent neural (NTK) sur des tâches possédant une structure compositionnelle ou hiérarchique. Si la littérature existante attribue largement les écarts entre noyaux et réseaux à la malédiction de la dimensionnalité (où les noyaux peinent à traiter les projections de faible dimension d'entrées de haute dimension), un compte quantitatif de cet écart à dimension d'entrée fixe — spécifiquement piloté par la profondeur du réseau et la structure compositionnelle — faisait défaut. Cet article répond à la question suivante : Sur quels objectifs, et à quel point, le NTK est-il sous-optimal, et quelle propriété spécifique de ces objectifs empêche le noyau de les exploiter ?

Méthodologie et Configuration
Les auteurs analysent ce problème sur le cercle unité $S^1$ , où le NTK admet une description de Fourier limpide. Ils introduisent une dichotomie entre deux mesures de complexité pour une fonction cible $f^*$ :

Complexité de Fourier : Contrôle le coût de l'apprentissage via le NTK (régime paresseux ou lazy regime). La norme de l'espace de Hilbert reproduisant le noyau (RKHS) du NTK est montrée comme étant équivalente (à une constante dépendant de la profondeur) à la norme de Sobolev $H^1$ , qui pénalise les oscillations de haute fréquence.
Complexité Architecturale : Contrôle le coût de l'apprentissage via un entraînement avec décroissance des poids (weight-decay) dans le régime « riche ». Elle est mesurée par la norme de variation profonde ( $RBV^2_{deep}$ ), qui quantifie la taille du plus petit réseau ReLU de profondeur $L$ et de largeur $w$ requis pour construire la cible.

Les auteurs définissent la classe d'architecture $\mathcal{C}_{L,w,R}$ comme étant des réseaux ReLU de profondeur $L$ , de largeur $w$ et de norme de variation profonde $R$ bornée. Ils comparent la complexité d'échantillonnage de l'estimateur NTK (régression par noyau Ridge) par rapport à la borne inférieure minimax pour cette classe d'architecture.

Contributions Clés

Caractérisation Minimax des Classes d'Architectures Profondes :
L'article établit le taux minimax $L^2$ pour la classe $\mathcal{C}_{L,w,R}$ . Le taux est fixé entre $\Omega(Lw^2R^2/n)$ et $\tilde{O}(L^2w^2R^2/n)$ . Ce résultat est serré à un facteur $L$ près, représentant le plancher statistique pour tout estimateur sur cette classe. Notamment, ce taux est indexé par des paramètres architecturaux $(L, w, R)$ plutôt que par des exposants de lissage de la cible.
Sous-optimalité Exponentielle du NTK :
Les auteurs prouvent que l'estimateur NTK se situe exponentiellement au-dessus du plancher minimax dès lors que la complexité de Fourier et la complexité architecturale de la cible se découplent. Spécifiquement, pour une cible ayant une fréquence dominante $k^*$ , le NTK nécessite $\Omega((k^*)^2)$ échantillons, tandis que la classe d'architecture ne nécessite que des ressources polynomiales par rapport à ses paramètres structurels.
- Le Témoin : La fonction en dents de scie itérée de profondeur $L$ (Telgarsky 2016) sert de témoin analytique. Elle peut être construite par un réseau de largeur 2 et de profondeur $L$ avec $O(L)$ poids (faible complexité architecturale) mais oscille $2^{L-1}$ fois (haute complexité de Fourier).
- L'Écart : Pour la fonction en dents de scie, le NTK nécessite $\Omega(4^L)$ échantillons, alors que le plancher minimax est polynomial en $L$ (entre $L^3$ et $L^4$ ). Cela produit une séparation exponentielle dans la complexité d'échantillonnage.
Validation Empirique :
Des expériences numériques confirment les affirmations théoriques sur trois fronts :
- Spectre du NTK : La décroissance des valeurs propres du NTK sur $S^1$ suit la décroissance prédite de $k^{-2}$ , confirmant le phénomène « la profondeur égale la platitude » (deep equals shallow) où la profondeur ne modifie pas le taux de décroissance spectrale.
- Cibles Lisses : Sur des cibles à bande limitée (lisses), le NTK est compétitif ou meilleur que les réseaux larges, ne présentant aucun écart exponentiel.
- Cibles Compositionnelles : Sur le modèle de parité parcimonieuse sur l'hypercube (un domaine différent où la SGD est connue pour réussir), un réseau standard à deux couches bat le NTK de quatre à six ordres de grandeur en erreur de test, réalisant la séparation prédite de bout en bout.

Résultats et Signification
L'article conclut que l'écart de performance entre le NTK et les réseaux entraînés n'est pas un phénomène générique « noyau contre réseau », mais une propriété d'espace de fonctions spécifique. L'écart provient d'un déphasage entre le biais de lissage inhérent au noyau (favorisant les fonctions de basse fréquence) et la structure compositionnelle de la cible (qui peut générer des oscillations de haute fréquence à faible coût architectural).

Insight Théorique : Ce travail fournit un mécanisme précis expliquant pourquoi la profondeur aide : elle permet aux réseaux de représenter des fonctions oscillatoires de haute fréquence à moindre coût via la composition, une capacité que le NTK (qui se comporte comme un noyau de Sobolev fixe) ne possède pas.
Plancher Minimax : La dérivation du taux minimax pour l'espace de variation profonde est présentée comme une contribution autonome, offrant une estimation directe, sans recours aux noyaux, de la complexité d'échantillonnage pour les problèmes compositionnels basée sur les paramètres architecturaux.
Portée : Les auteurs précisent que l'écart n'est pas universel ; il disparaît pour les cibles lisses et à bande limitée, où les complexités de Fourier et architecturale sont alignées. De plus, ils distinguent les limites statistiques de la faisabilité algorithmique, notant que si la fonction en dents de scie est statistiquement apprenable par la classe d'architecture, elle est notoirement difficile à optimiser par la descente de gradient, contrairement à la parité parcimonieuse qui est à la fois statistiquement et algorithmiquement apprenable.

En résumé, l'article soutient que le NTK est proche de l'optimalité pour les cibles de l'espace $H^1$ , mais exponentiellement sous-optimal pour les cibles où la structure compositionnelle permet des représentations de haute fréquence « peu coûteuses », un régime où l'entraînement en mode riche est statistiquement nécessaire.