🤖 machine learning

Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View

Cet article soutient que lorsque l'efficacité de l'approximation est évaluée par la complexité bit de calcul plutôt que par le nombre de paramètres, aucune méthode ne surpasse fondamentalement les limites intrinsèques imposées par l'entropie métrique, révélant que les avantages perçus des réseaux de neurones découlent souvent de différences dans la complexité de la classe de fonctions plutôt que d'une supériorité architecturale, et recadrant la traditionnelle « malédiction de la dimensionnalité » comme une « malédiction de la complexité bit » plus fondamentale.

Auteurs originaux : Tong Mao, Jinchao Xu

Publié 2026-08-04

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tong Mao, Jinchao Xu

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

Imaginez que vous essayiez de décrire un objet complexe et de haute dimension — comme une galaxie tourbillonnante ou un gâteau à plusieurs couches — à un ami qui ne peut comprendre que des dessins simples et plats. Dans le monde de l'informatique et des mathématiques, c'est ce qu'on appelle un « problème d'approximation de haute dimension ». Pendant des décennies, les scientifiques ont lutté contre un ennemi redoutable appelé la « malédiction de la dimensionnalité ». Le nom semble effrayant, mais l'idée est simple : à mesure que le nombre de variables (ou de dimensions) dans un problème augmente, la quantité d'informations nécessaires pour le décrire avec précision explose. C'est comme essayer de peindre le portrait d'un objet en 100 dimensions ; le nombre de coups de pinceau requis semble croître si vite qu'il devient impossible de terminer le travail.

Pendant longtemps, la méthode standard pour mesurer la capacité d'un ordinateur à résoudre ces problèmes consistait à compter les « paramètres ». Considérez les paramètres comme les boutons, les cadrans et les réglages sur une machine. Si une méthode utilise moins de boutons pour obtenir le même résultat, elle est considérée comme plus efficace. Récemment, les réseaux de neurones (les systèmes d'IA qui alimentent des choses comme la reconnaissance d'images ou les modèles de langage) ont été célébrés parce qu'ils semblent briser cette malédiction. Ils semblent résoudre des problèmes de haute dimension avec un nombre de boutons qui n'explose pas à mesure que les dimensions augmentent, ce qui a conduit beaucoup de gens à croire qu'ils avaient trouvé la clé magique pour déverrouiller les problèmes les plus complexes de la science.

Cependant, il y a un piège qui est souvent négligé dans l'enthousiasme général. Dans le monde réel, les ordinateurs ne stockent pas les nombres avec une précision infinie ; ils les stockent sous forme de chaînes de 0 et de 1, ou « bits ». Chaque bouton de cette machine doit être encodé dans un nombre spécifique de bits pour être stocké et calculé. Cet article pose une question fondamentale : si nous arrêtons de compter simplement les boutons et que nous commençons à compter les bits d'information réels nécessaires pour les stocker, les réseaux de neurones ont-ils toujours l'air magiques ? Les auteurs, Tong Mao et Jinchao Xu, explorent cette question en profondeur, en utilisant un concept appelé « entropie métrique » (qui mesure essentiellement la quantité minimale d'informations nécessaires pour décrire une forme ou une fonction) pour voir si les réseaux de neurones battent réellement la malédiction ou s'ils cachent simplement le coût d'une autre manière.

Le grand braquage du comptage de bits

Les auteurs de cet article, Tong Mao et Jinchao Xu, ont décidé d'enfiler leurs chapeaux de détectives et d'examiner la « malédiction de la dimensionnalité » sous un nouvel angle. Au lieu de simplement compter combien de paramètres (boutons) une méthode utilise, ils se sont demandé : « Combien de bits de mémoire faut-il réellement pour stocker ces boutons et obtenir une bonne réponse ? »

Pour comprendre leur enquête, imaginez que vous essayez de décrire une colline douce et vallonnée à un robot.

L'ancienne méthode (Compter les paramètres) : Vous pourriez dire : « J'ai besoin de 100 points pour décrire cette colline. » Si vous passez à une nouvelle méthode, comme un réseau de neurones, et que vous dites : « Je n'ai besoin que de 10 points », vous avez l'impression d'avoir gagné. Vous avez vaincu la malédiction !
La nouvelle méthode (Compter les bits) : Mais attendez. Et si ces 10 points étaient incroyablement sensibles ? Et si, pour décrire la forme de la colline avec précision, chacun de ces 10 points devait être stocké avec une précision extrême — par exemple, en ayant besoin de 1 000 bits pour chaque point ? Soudain, vous n'utilisez pas 10 unités d'information, mais 10 000. Pendant ce temps, l'ancienne méthode utilisait 100 points, mais chacun n'avait besoin que de 10 bits. Finalement, l'« ancienne » méthode utilisait en réalité moins de bits au total.

L'article soutient que, pendant longtemps, nous avons été trompés par le « nombre de paramètres ». Nous avons vu les réseaux de neurones utiliser moins de boutons et avons supposé qu'ils étaient plus efficaces. Mais lorsque les auteurs ont mesuré l'efficacité en termes de bits (la véritable monnaie de l'informatique), l'histoire a changé.

La « magie » qui n'en est pas vraiment une

Les chercheurs ont examiné deux types principaux de « magie » pour lesquels les réseaux de neurones étaient célèbres :

Taux indépendants de la dimension : Certaines études affirmaient que les réseaux de neurones pouvaient approximer certaines fonctions complexes sans que leurs performances ne se dégradent à mesure que le nombre de dimensions augmentait. On aurait dit qu'ils avaient trouvé un moyen d'ignorer totalement la taille du problème.
Superconvergence : C'est l'idée selon laquelle les réseaux de neurones profonds (des réseaux avec de nombreuses couches) peuvent approximer des fonctions lisses beaucoup plus rapidement que les méthodes traditionnelles comme les polynômes ou les éléments finis. On aurait dit qu'ils dépassaient la concurrence en trombe.

L'enquête des auteurs a révélé que ces « superpouvoirs » sont largement une illusion créée par la façon dont nous mesurons les choses.

Lorsqu'ils ont analysé l'entropie métrique — un terme sophistiqué pour désigner la complexité intrinsèque de la classe de fonctions étant approximée — ils ont découvert que les fonctions que les réseaux de neurones sont doués d'approximer (comme celles dans les « espaces de Barron ») sont en fait simplement moins complexes que les fonctions que les méthodes traditionnelles peinent à traiter. Ce n'est pas que le réseau de neurones est un meilleur artiste ; c'est que le tableau qu'on lui demande de copier est moins détaillé que celui que l'artiste traditionnel essayait de copier. La vitesse « indépendante de la dimension » n'est pas due au fait que le réseau est spécial ; c'est parce que la cible était facile dès le départ.

Le piège des réseaux profonds

La découverte la plus surprenante concerne les réseaux de neurones profonds. Ce sont les réseaux dotés de nombreuses couches qui font l'objet de toute l'agitation médiatique. L'article montre que, bien que les réseaux profonds puissent effectivement atteindre un taux d'erreur plus rapide lorsqu'ils sont mesurés par le nombre de paramètres (les « boutons »), cette vitesse s'accompagne d'une taxe cachée.

Parce que les réseaux profonds sont si complexes et sensibles, les nombres qu'ils contiennent (les poids et les biais) doivent être stockés avec une précision beaucoup plus élevée pour éviter les erreurs. Les auteurs ont prouvé que le nombre de bits requis pour stocker ces paramètres augmente de manière explosive à mesure que le réseau devient plus profond.

Voyez cela ainsi : un réseau peu profond est comme un pont en bois robuste. Il nécessite beaucoup de planches (paramètres), mais chaque planche est facile à mesurer et à stocker. Un réseau profond est comme un pont en verre. Il utilise moins de planches, mais chaque planche est si fragile et précise qu'il faut un scanner laser pour la mesurer. Si vous essayez de construire le pont en verre avec un ruban à mesurer standard (une précision finie), il s'effondre.

L'article démontre que lorsque l'on compte le nombre total de bits nécessaires pour construire ce pont en verre, l'« efficacité » disparaît. Les bits supplémentaires nécessaires pour maintenir la stabilité du réseau profond annulent l'avantage d'avoir moins de paramètres. En fait, pour de nombreux problèmes standards, les réseaux profonds finissent par nécessiter autant de bits, voire plus, que les méthodes classiques comme les polynômes ou les éléments finis.

Le verdict : C'est un peu la malédiction

Alors, les réseaux de neurones battent-ils la malédiction de la dimensionnalité ? Selon Mao et Xu, la réponse est non, du moins pas de la manière dont nous le pensions.

La « malédiction » n'est pas vraiment liée au nombre de dimensions. Elle est liée à la complexité en bits. La limite fondamentale de la capacité à approximer une fonction est déterminée par la quantité d'informations (les bits) que cette fonction contient réellement. Cela est régi par l'« entropie métrique ».

Si une fonction est complexe, elle nécessite beaucoup de bits pour être décrite, quel que soit l'outil utilisé.
Si une fonction est simple, elle nécessite moins de bits.

Les réseaux de neurones ne changent pas les règles du jeu ; ils changent simplement la façon dont on compte les points. Lorsque nous regardons le jeu à travers le prisme des bits plutôt que des paramètres, la « supériorité » des réseaux de neurones disparaît souvent. Les avantages apparents, comme les taux indépendants de la dimension ou la superconvergence, sont souvent dus au fait que les réseaux de neurones sont testés sur des classes de fonctions qui sont intrinsèquement moins complexes (ont une entropie métrique plus faible) que celles sur lesquelles les méthodes traditionnelles sont testées.

Pourquoi cela importe

Cet article ne dit pas que les réseaux de neurones sont inutiles. Il dit que nous devons être plus intelligents dans la façon dont nous les évaluons. Dans le monde réel, les ordinateurs ont une mémoire finie. Ils ne peuvent pas stocker une précision infinie. Si une méthode semble excellente sur le papier parce qu'elle utilise moins de paramètres, mais qu'elle nécessite une quantité massive de mémoire pour stocker ces paramètres avec précision, elle n'est peut-être pas le meilleur choix pour une application réelle.

Les auteurs suggèrent que la « malédiction de la dimensionnalité » est en réalité une « malédiction de la complexité en bits ». La véritable limite n'est pas le nombre de dimensions que vous avez, mais le nombre de bits dont vous avez besoin pour décrire le problème. En déplaçant notre attention du comptage des boutons vers le comptage des bits, nous obtenons une image beaucoup plus claire et plus réaliste de ce que ces outils puissants peuvent et ne peuvent pas faire. C'est un rappel que dans le monde des mathématiques de haute dimension, le diable est toujours dans les détails — et ces détails se mesurent en bits.

Résumé Technique : Les réseaux de neurones battent-ils réellement la malédiction de la dimensionnalité ? Une perspective par la complexité en bits

1. Énoncé du problème

L'approximation de haute dimension est un défi central en calcul scientifique et en apprentissage automatique, traditionnellement entravé par la « malédiction de la dimensionnalité ». Dans la théorie de l'approximation classique, le nombre de degrés de liberté ( $N$ ) requis pour atteindre une précision donnée croît souvent de manière exponentielle avec la dimension ( $d$ ). Par exemple, dans les espaces de Sobolev $H^r([0,1]^d)$ , le taux de convergence optimal pour les méthodes classiques (polynômes, éléments finis) suit une échelle en $O(N^{-r/d})$ , où l'exposant se détériore à mesure que $d$ augmente.

La littérature récente suggère que les réseaux de neurones (tant peu profonds que profonds) peuvent surmonter cette malédiction, présentant des taux indépendants de la dimension ou une « superconvergence » (par exemple, atteignant $O(N^{-2r/d})$ pour les réseaux ReLU profonds dans les espaces de Sobolev). Cependant, ces résultats sont généralement mesurés en termes de nombre de paramètres ( $N$ ).

Le présent article identifie une lacune critique : le calcul pratique opère sous une précision finie. Les paramètres doivent être encodés à l'aide d'un nombre fini de bits. Les auteurs soutiennent que mesurer l'efficacité uniquement par le nombre de paramètres est trompeur car cela ignore la complexité en bits requise pour représenter ces paramètres avec une précision suffisante. Le problème central est de réévaluer les taux d'approximation à travers le prisme de la complexité en bits de calcul et de l'entropie métrique afin de déterminer si les réseaux de neurones possèdent réellement un avantage intrinsèque sur les méthodes classiques.

2. Méthodologie

Les auteurs développent un cadre d'approximation unifié basé sur l'encodage binaire et l'entropie métrique.

2.1 Entropie métrique et complexité en bits

L'outil théorique central est l'entropie mételle (ou nombre d'entropie dyadique) $\epsilon_m(K)_X$ , défini comme le rayon minimal $\epsilon$ tel qu'un ensemble compact $K$ dans un espace de Banach $X$ puisse être recouvert par $2^m$ boules de rayon $\epsilon$ .

Proposition 2 établit que $\epsilon_m(K)_X$ est quantitativement équivalent à l'erreur d'approximation optimale réalisable avec $m$ bits. Ainsi, l'entropie métrique caractérise le contenu informationnel intrinsèque (complexité en bits) d'une classe de fonctions.
L'article distingue entre les taux basés sur les paramètres (convergence en termes de $N$ ) et les taux basés sur les bits (convergence en termes de $N_b$ , le nombre total de bits).

2.2 Analyse de l'encodage

La méthodologie consiste à analyser comment les approximations classiques et celles par réseaux de neurones se traduisent en représentations à bits finis :

Représentation des paramètres : Une méthode d'approximation associe une fonction $f$ à un ensemble de paramètres $\Theta \in \mathbb{R}^N$ .
Quantification : Les paramètres sont quantifiés à $\tau$ bits chacun, ce qui donne un budget total de bits $N_b = N\tau$ .
Analyse de stabilité : Les auteurs analysent la constante de Lipschitz (sensibilité) de la carte de reconstruction $\tilde{S}_N$ . Si la reconstruction est hautement sensible aux perturbations des paramètres, un $\tau$ plus grand (plus de bits par paramètre) est nécessaire pour maintenir une tolérance d'erreur spécifique.
Bornes inférieures : En utilisant le Lemme 2, l'article dérive des bornes inférieures pour les erreurs d'approximation basées sur la différence entre l'entropie métrique de la classe de fonctions cible et l'entropie métrique de la classe d'approximation.

3. Contributions clés et résultats

3.1 Méthodes classiques (Polynômes, FEM, Grilles éparses)

L'article analyse les méthodes classiques (approximation polynomiale, éléments finis, grilles éparses) sous le cadre de la complexité en bits.

Résultat : Pour les méthodes classiques approximant les espaces de Sobolev $H^r$ , le taux basé sur les paramètres est $O(N^{-r/d})$ . Lorsqu'elles sont converties en taux basés sur les bits, la convergence devient $O((N_b / \log N_b)^{-r/d})$ .
Suboptimalité : Les auteurs montrent que ces méthodes sont généralement suboptimales par rapport aux limites intrinsèques de l'entropie métrique des classes de fonctions. L'entropie métrique de $H^r$ décroît en $m^{-r/d}$ , mais les méthodes classiques échouent souvent à atteindre ce taux lorsque les contraintes de bits sont considérées, particulièrement en raison de la surcharge logarithmique de l'encodage des paramètres.

3.2 Réseaux de neurones : peu profonds et profonds

L'article réévalue les performances des réseaux de neurones (ReLU et $\text{ReLU}^k$ ) sur les espaces de Barron et les espaces de Sobolev.

Réseaux peu profonds sur les espaces de Barron :
- Les réseaux peu profonds atteignent des taux basés sur les paramètres de $O(N^{-1/2 - (2k+1)/2d})$ sur les espaces de Barron.
- Perspective de la complexité en bits : En tenant compte de l'encodage par bits, le taux reste comparable à l'entropie métrique de l'espace de Barron. L'apparence d'« indépendance de la dimension » est attribuée à la faible entropie métrique de l'espace de Barron lui-même, et non à une supériorité architecturale. La classe cible est simplement moins complexe que l'espace de Sobolev.
Réseaux profonds et superconvergence :
- Il a été démontré que les réseaux ReLU profonds peuvent atteindre des taux de « superconvergence » de $O(N^{-2r/d})$ dans les espaces de Sobolev, doublant apparemment l'exposant par rapport aux méthodes classiques.
- Perspective de la complexité en bits : Les auteurs démontrent que cette amélioration est un artefact du comptage des paramètres. Le Lemme 1 prouve que la carte de reconstruction pour les réseaux profonds présente une sensibilité exponentielle aux perturbations des paramètres (la constante de Lipschitz croît comme $(n+1)(W+1)^{n+1}M^{n+1}$ ).
- Pour maintenir la même précision, la précision requise (bits par paramètre) croît polynomialement avec la taille du réseau. Par conséquent, le taux basé sur les bits pour les réseaux profonds se dégrade pour devenir $O(N_b^{-2r/3d})$ (ou similaire, selon les constantes), ce qui ne surpasse pas le taux classique de $O(N_b^{-r/d})$ . La « superconvergence » est compensée par le coût massif en bits requis pour une représentation stable en précision finie.

3.3 Bornes inférieures et optimalité

En utilisant le cadre de l'entropie métrique, l'article établit des bornes inférieures fondamentales :

Aucune méthode ne peut fondamentalement dépasser l'ordre d'approximation dicté par l'entropie métrique de la classe de fonctions cible.
De nombreux avantages apparents des réseaux de neurones (indépendance de la dimension, superconvergence) proviennent de l'analyse de classes de fonctions ayant une complexité intrinsèque plus faible (ex: espaces de Barron) ou de l'omission du coût en bits de la stabilité (dans le cas des réseaux profonds).

4. Signification et conclusions

L'article conclut que la « malédiction de la dimensionnalité » n'est pas une propriété intrinsèque de l'approximation de haute dimension, mais plutôt une malédiction de la complexité en bits régie par l'entropie métrique.

Recadrage de la malédiction : La limitation fondamentale n'est pas la dimension $d$ elle-même, mais l'entropie métrique de la classe de fonctions approximée. Si une classe de fonctions possède une faible entropie métrique (comme les espaces de Barron), elle peut être approximée efficacement quelle que soit la dimension.
Limitations des réseaux de neurones : Les réseaux de neurones ne possèdent pas d'avantage architectural intrinsèque leur permettant de contourner les limites fixées par l'entropie métrique.
- Leur succès sur des classes spécifiques (Barron) est dû à la faible complexité de ces classes.
- Leur « superconvergence » dans les réseaux profonds est une illusion de comptage de paramètres qui disparaît lorsque les contraintes de précision finie (complexité en bits) sont appliquées.
Implication pratique : Dans le calcul pratique en précision finie, le coût en bits pour représenter les paramètres est le véritable goulot d'étranglement. Les méthodes qui semblent supérieures en nombre de paramètres peuvent être inférieures en complexité en bits en raison de leur instabilité.

Les auteurs affirment qu'une vue unifiée basée sur l'entropie métrique et la complexité en bits fournit un cadre plus précis et plus réaliste pour évaluer les méthodes d'approximation, révélant que les méthodes classiques traditionnelles et les réseaux de neurones sont soumis aux mêmes limites fondamentales de l'information.