🔢 mathematics

Compositional Approximation Can Strictly Outperform Superpositional Approximation

Cet article démontre que pour des classes de fonctions spécifiques possédant des propriétés structurelles particulières, les méthodes d'approximation compositionnelles (telles que les réseaux de neurones) peuvent atteindre des taux d'approximation arbitrairement meilleurs que les méthodes de superposition optimales, lesquelles reposent sur des combinaisons linéaires d'éléments de dictionnaires.

Auteurs originaux : Dennis Elbrächter, Philipp Petersen

Publié 2026-06-09

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Dennis Elbrächter, Philipp Petersen

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

La vue d'ensemble : Deux façons de construire une maison

Imaginez que vous essayiez de construire une réplique parfaite d'une maison très complexe et détaillée (ce qui représente une fonction ou un motif dans les données). Vous avez une boîte à outils remplie de blocs de construction simples (comme des briques, des poutres ou des carreaux).

L'article compare deux stratégies différentes pour construire cette maison :

La stratégie « Superpositionnelle » (Le tas linéaire) : Vous prenez vos blocs simples et vous les empilez simplement les uns sur les autres, en les mélangeant en un seul gros tas. Vous pouvez ajuster le nombre de chaque bloc utilisé, mais vous ne faites essentiellement que les additionner. C'est ainsi que fonctionnent les méthodes mathématiques traditionnelles (comme les séries de Fourier).
La stratégie « Compositionnelle » (L'assemblage par couches) : Vous construisez la maison par couches. Vous prenez un bloc, vous lui donnez une forme, puis vous utilisez cette pièce façonnée comme fondation pour la couche suivante, que vous façonnez à nouveau, et ainsi de suite. C'est ainsi que fonctionnent les réseaux de neurones. Ils ne se contentent pas d'ajouter des blocs ; ils les composent, en injectant la sortie d'une couche dans la suivante.

Le problème : Quand le « Tas » échoue

Pour beaucoup de formes simples (comme des courbes lisses), les deux stratégies fonctionnent à peu près de la même manière. On peut construire une bonne approximation avec l'une ou l'autre méthode.

Cependant, les auteurs ont découvert un type spécifique de « maison » (une classe spécifique de fonctions mathématiques) où la Stratégie du Tas se heurte à un mur infranchissable, tandis que la Stratégie par Couches passe droit devant elle.

L'analogie de la foule « presque orthogonale » :
Imaginez que vous essayiez de décrire une foule de personnes debout dans une pièce.

La Stratégie du Tas : Vous essayez de décrire tout le monde en choisissant quelques personnes « types » dans un dictionnaire et en les additionnant. Si les personnes dans la foule font toutes face à des directions complètement différentes (mathématiquement « orthogonales »), vous aurez besoin d'un nombre immense de personnes types pour les décrire toutes. C'est comme essayer de décrire une foule où chacun fait face à une direction unique ; vous avez besoin d'une description unique pour presque tout le monde.
Le rebondissement : Les auteurs ont créé un scénario où les gens font presque face à des directions différentes, mais pas tout à fait. Ils sont « presque orthogonaux ».
- Dans un Tas, c'est un cauchemar. Parce qu'ils sont si différents les uns des autres, vous ne pouvez pas réutiliser vos blocs standards efficacement. Vous avez besoin d'un dictionnaire massif de blocs pour couvrir tout le monde, et le nombre de blocs nécessaires augmente de manière explosive à mesure que la pièce s'agrandit.
- Dans une approche par Couches, vous pouvez construire une « machine » qui génère ces personnes. Vous n'avez pas besoin d'un bloc unique pour chaque personne ; vous avez juste besoin de quelques règles simples (couches) qui, lorsqu'elles sont empilées, peuvent générer ces directions « presque différentes ».

La découverte principale : L'écart

L'article prouve mathématiquement que pour ces fonctions spécifiques d'« presque orthogonalité » :

Les méthodes de superposition (Le Tas) : L'erreur (la qualité de l'approximation) reste élevée à moins d'utiliser un nombre massif et ingérable de paramètres. L'efficacité est strictement limitée.
Les méthodes compositionnelles (Les Couches/Les Réseaux de Neurones) : Vous pouvez atteindre le même niveau de précision avec beaucoup moins de paramètres.

Les auteurs ont construit des exemples explicites où l'écart entre les deux méthodes est arbitrairement grand. Vous pouvez rendre la méthode du « Tas » infiniment pire que la méthode « par Couches » simplement en modifiant la structure de la fonction.

Pourquoi cela arrive-t-il ? (La géométrie du problème)

L'article utilise un concept appelé nombres de recouvrement (une façon sophistiquée de mesurer la « taille » ou la complexité d'un ensemble de formes).

Le Tas : Pour couvrir toutes les formes possibles dans cette classe de fonctions, la méthode du Tas doit couvrir une zone massive. C'est comme essayer de couvrir une forêt immense et tentaculaire avec quelques petites tentes. Il vous faut des milliers de tentes.
Les Couches : La méthode Compositionnelle réalise que ces formes ne sont pas aléatoires ; elles possèdent une structure cachée (auto-similarité). C'est comme réaliser que la forêt est en fait composée de motifs d'arbres répétitifs. Au lieu de couvrir toute la forêt avec des tentes, vous avez juste besoin d'un plan pour construire les arbres. La méthode « par Couches » peut naviguer dans cette structure efficacement, nécessitant une infime fraction des ressources.

La contrainte « Riesz »

L'article précise que cet avantage est maintenu même si nous restreignons la méthode du « Tas » pour qu'elle soit très bien structurée (satisfaisant mathématiquement une « condition de Riesz », ce qui garantit que les blocs ne sont pas étrangement redondants ou défectueux). Même avec le meilleur dictionnaire de blocs possible, la méthode du Tas ne peut pas rattraper la méthode par Couches pour ces fonctions spécifiques.

Résumé

La revendication : Les réseaux de neurones (méthodes compositionnelles) ne sont pas seulement « assez bons » pour tout ; ils sont strictement supérieurs pour une classe de problèmes mathématiquement définis.
La raison : Ces problèmes possèdent une structure cachée et stratifiée qui permet de construire des choses complexes à partir d'étapes simples.
La limitation : Les méthodes traditionnelles qui se contentent d'additionner des éléments (superposition) ne peuvent pas exploiter cette structure efficacement. Elles restent bloquées à essayer de décrire chaque petite variation individuellement, ce qui entraîne un gaspillage massif de ressources.

En bref : Si le problème est construit comme une poupée russe (des couches à l'intérieur de couches), une méthode qui construit par couches gagne. Si vous essayez de résoudre le problème en jetant simplement toutes les poupées dans un tas, vous échouerez en termes d'efficacité, peu importe le nombre de poupées que vous possédez.

Résumé technique : L'approximation compositionnelle peut surpasser strictement l'approximation superpositionnelle

Énoncé du problème
L'article traite d'une question fondamentale de la théorie de l'approximation : dans quelles conditions les méthodes compositionnelles (telles que les réseaux de neurones) offrent-elles des taux d'approximation strictement supérieurs aux méthodes superpositionnelles (combinaisons linéaires d'éléments d'un dictionnaire, par exemple l'approximation à $M$ -termes). Bien que les preuves empiriques suggèrent que les réseaux de neurones sont puissants, les justifications théoriques reposent souvent sur l'émulation de méthodes existantes, atteignant des taux comparables mais non supérieurs. De plus, de nombreuses classes de fonctions classiques admettent des dictionnaires qui produisent des taux d'approximation à $M$ -termes optimaux. Les auteurs cherchent à identifier les propriétés structurelles des classes de fonctions où l'approximation compositionnelle peut surpasser strictement toute approximation superpositionnelle, même sous des contraintes garantissant un codage efficace par chaîne de bits des paramètres (empêchant ainsi une construction de dictionnaire par « force brute » triviale).

Méthodologie et cadre
Les auteurs établissent un cadre mathématique rigoureux au sein d'un espace de Hilbert $H$ pour comparer les schémas d'approximation :

Taux d'approximation : Ils définissent le taux d'approximation $\gamma(C, S)$ comme l'ordre de décroissance polynomiale de l'erreur uniforme en fonction du budget de paramètres $M$ .
Schémas superpositionnels : Ils sont définis comme des combinaisons linéaires à $M$ -termes d'éléments d'un dictionnaire $D = (\phi_i)_{i \in \mathbb{N}}$ , soumis à une contrainte de « recherche de profondeur polynomiale ». Cette contrainte limite les indices et la taille des coefficients des éléments du dictionnaire à un polynôme de $M$ , garantissant que l'approximant peut être encodé sous la forme d'une chaîne de bits de longueur $O(M \log^q M)$ . Le taux d'approximation de Riesz ( $\gamma_{\text{Riesz}}$ ) est la borne supérieure des taux réalisables par tout dictionnaire satisfaisant une borne de Riesz inférieure (garantissant la stabilité).
Schémas compositionnels : Ils sont modélisés via des réseaux de neurones avec des contraintes sur la profondeur (polylogarithmique en $M$ ), la connectivité (linéaire en $M$ ) et la magnitude des poids (polynomiale en $M$ ). Cela assure une efficacité de codage par chaîne de bits similaire.
Perspective géométrique : L'intuition théorique centrale repose sur la géométrie asymptotique de la classe de fonctions. Les auteurs soutiennent que si une classe de fonctions peut être $\epsilon$ -approximée par une union d'un nombre limité de sous-espaces linéaires de faible dimension (une structure exploitable par composition) mais nécessite un sous-espace linéaire de haute dimension pour une approximation linéaire, un écart dans les taux peut exister. Ceci est lié au concept de « nombres de recouvrement », où l'ensemble non linéaire des approximants est dérisoire par rapport à l'espace linéaire nécessaire lorsque $\epsilon \to 0$ .

Contributions clés et résultats

La construction SPOON : Les auteurs introduisent une structure d'ensemble prototypique appelée SPOON (Superpolynomially growing almost Orthogonal sequeNce — Séquence presque orthogonale à croissance superpolynomiale). Une SPOON consiste en une séquence d'ensembles $V_m$ où :
- La cardinalité croît de manière superpolynomiale ( $|V_m| \ge 2^{m^\alpha}$ ).
- Les éléments ont des normes décroissant en $m^{-\mu}$ .
- Les éléments sont presque orthogonaux à $\eta$ près, le produit scalaire décroissant selon $m^{-\nu}$ .
Borne supérieure sur les taux superpositionnels (Théorème 3.4) : Le résultat théorique central prouve que si une classe de fonctions $C$ contient une $(\mu, \nu)$ -SPOON, le meilleur taux d'approximation de Riesz réalisable est borné par :
$\gamma_{\text{Riesz}}(C) \le \frac{1}{2} + \frac{\mu}{\nu}$
La preuve utilise un argument par l'absurde impliquant la géométrie des ensembles presque orthogonaux et les propriétés des dictionnaires de Riesz. Elle démontre que tout dictionnaire satisfaisant la condition de Riesz ne peut pas couvrir efficacement les ensembles presque orthogonaux exponentiellement grands au sein de la SPOON en utilisant seulement un nombre polynomial de termes.
Construction explicite (Section 4) : Les auteurs construisent des classes de fonctions explicites $V(k, \alpha, \beta, \mu)$ en utilisant des compositions de fonctions « chapeau » $f$ . Ces classes sont formées par des compositions itérées de fonctions définies par des vecteurs binaires.
- Ils prouvent que ces classes contiennent de grands ensembles de fonctions presque orthogonales satisfaisant les conditions de la SPOON.
- Ils démontrent que les réseaux de neurones ReLU peuvent approximer ces classes avec un taux de $\gamma_{\rho}^N \ge \frac{\mu}{\alpha}$ .
- En combinant cela avec la borne supérieure, ils montrent que pour des choix de paramètres spécifiques (par exemple, $\mu = \sqrt{k}$ ), l'écart entre les taux de composition et de Riesz devient arbitrairement grand à mesure que la profondeur de composition $k$ augmente. Spécifiquement, $\lim_{k \to \infty} \gamma_{\rho}^N = \infty$ tandis que $\lim_{k \to \infty} \gamma_{\text{Riesz}} \le \frac{1}{2}$ .
Exemple d'orthogonalité pathologique (Annexe A) : L'article présente également un exemple plus simple, bien que plus pathologique, impliquant un système orthonormé où les coefficients décroissent logarithmiquement. Dans ce cas, l'approximation superpositionnelle produit un taux de $-\infty$ (aucune décroissance polynomiale), tandis que les réseaux de neurones atteignent un taux positif, soulignant la difficulté que rencontrent les méthodes superpositionnelles face à des structures hautement orthogonales.

Signification et revendications
L'article affirme fournir les premiers exemples explicites de classes de fonctions où l'approximation compositionnelle surpasse strictement l'approximation superpositionnelle, même lorsque la méthode superpositionnelle est autorisée à choisir le dictionnaire optimal sous des contraintes de stabilité (Riesz) et d'encodage.

La signification réside dans l'identification d'une propriété structurelle spécifique — la présence de grands ensembles presque orthogonaux au sein de sous-espaces de dimension finie — qui est intrinsèquement difficile à capturer efficacement par des combinaisons linéaires, mais qui est naturellement gérée par la composition hiérarchique de blocs de construction simples. Les auteurs soutiennent que ce décalage structurel explique pourquoi les réseaux de neurones peuvent atteindre de meilleurs taux sans dépendre de l'instabilité ou d'un encodage de paramètres non borné. Ce travail suggère que l'avantage des réseaux de neurones n'est pas simplement l'approximation universelle, mais une adaptabilité géométrique spécifique à ces classes de fonctions présentant cette structure « presque orthogonale ».

Les auteurs restent modestes quant à la portée de leurs travaux, notant que leurs résultats s'appliquent aux classes de fonctions contenant ces structures SPOON spécifiques et que les limites actuelles des taux de superposition sont restreintes aux dictionnaires de Riesz, bien qu'ils pensent qu'il s'agisse d'une limitation technique plutôt que fondamentale. Ils ne prétendent pas que ces résultats s'appliquent à toutes les classes de fonctions ou que les réseaux de neurones sont universellement supérieurs, mais qu'ils sont supérieurs pour les classes présentant cette structure géométrique asymptotique spécifique.