🤖 machine learning

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

Cet article améliore la borne supérieure de l'exposant de la multiplication matricielle $\omega$ pour la ramener à moins de 2,371177 en reformulant le problème d'optimisation sous-jacent et en améliorant le processus de résolution grâce aux techniques modernes d'apprentissage automatique et à AlphaEvolve.

Auteurs originaux : Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

Publié 2026-08-18

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

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

Dans le vaste paysage de l'informatique, peu d'opérations sont aussi fondamentales que la multiplication de deux grandes grilles de nombres, un processus connu sous le nom de multiplication de matrices. Cette tâche mathématique sous-tend tout, de l'entraînement des modèles d'intelligence artificielle au rendu d'images réalistes dans les jeux vidéo. Depuis des décennies, les scientifiques savent que cette opération peut être effectuée plus rapidement que la méthode standard et directe, mais la limite précise de la vitesse à laquelle elle peut potentiellement atteindre un niveau reste l'un des mystères les plus tenaces du domaine. Cette limite est décrite par un nombre unique, un exposant mathématique qui dicte la manière dont le temps requis pour le calcul augmente à mesure que la taille des grilles augmente. Plus ce nombre est petit, plus l'ordinateur peut être efficace. Bien que le minimum théorique soit connu comme étant au moins de deux, la meilleure borne supérieure prouvée a stagné juste au-dessus de 2,37 pendant des années, une barrière que les chercheurs ont tenté de briser avec des outils mathématiques de plus en plus sophistiqués.

Une équipe de chercheurs de Google DeepMind, accompagnée de collaborateurs de plusieurs universités, a maintenant repoussé cette limite légèrement plus loin. En combinant des techniques d'optimisation modernes avec une nouvelle forme d'intelligence artificielle, ils ont établi un nouveau record, prouvant que l'exposant peut être abaissé à moins de 2,371177. Il s'agit d'un décalage numérique minime, mais dans le contexte de ce problème spécifique, cela représente une avancée significative. Le résultat précédent, obtenu en 2025, se situait à 2,371339. La nouvelle découverte ne résout pas le mystère ultime de la limite exacte, et ne change pas immédiatement la façon dont les ordinateurs multiplient les matrices en pratique, mais elle resserre les contraintes théoriques du problème, montrant que le plafond est plus bas que ce que l'on pensait possible auparavant.

Le chemin vers ce nouveau record a commencé avec un cadre mathématique connu sous le nom de méthode du laser, une technique développée il y a plus de quarante ans pour concevoir indirectement des algorithmes de multiplication de matrices plus rapides. Le raffinement le plus récent de cette méthode, appelé analyse de perte de combinaison (combination loss analysis), repose sur la résolution d'un problème d'optimisation massif et complexe. Ce problème consiste à trouver la meilleure façon de décomposer une grande structure mathématique en morceaux plus petits. Les chercheurs ont découvert que la difficulté de ce problème dépend d'un paramètre représentant la profondeur de la décomposition. Les tentatives précédentes s'étaient arrêtées à une profondeur de trois, ce qui limitait le nombre de variables ajustables. La nouvelle équipe a réalisé qu'en augmentant cette profondeur à quatre, elle pourrait explorer un espace de possibilités beaucoup plus vaste, mais qu'en faisant cela, elle devrait résoudre un problème comportant des millions de variables, une tâche bien trop grande pour les algorithmes traditionnels utilisés par le passé.

Pour faire face à cette échelle, les chercheurs se sont tournés vers des techniques empruntées à l'apprentissage automatique (machine learning). Au lieu d'utiliser des solveurs mathématiques standards, ils ont reformulé le problème afin qu'il puisse être traité par la descente de gradient, une méthode couramment utilisée pour entraîner des réseaux de neurones. Cette approche leur a permis d'utiliser la puissance du matériel informatique pour traiter les données en parallèle, gérant ainsi l'explosion de la complexité qui accompagnait la décomposition plus profonde. Ils ont traité les variables mathématiques comme s'il s'agissait des poids ajustables dans un modèle d'apprentissage, les affinant de manière itérative pour trouver une meilleure solution. Ce changement de stratégie a permis à lui seul d'améliorer la borne d'une quantité mesurable, démontant que les outils de calcul modernes pouvaient débloquer un potentiel que les anciennes méthodes avaient manqué.

Cependant, l'équipe ne s'est pas arrêtée là. Elle a employé un système appelé AlphaEvolve, une intelligence artificielle conçue pour écrire et améliorer son propre code. Plutôt que de simplement exécuter l'algorithme d'optimisation, ils ont laissé l'IA modifier l'algorithme lui-même. Le système générait une nouvelle version du code, l'exécutait pour voir quelle borne elle produisait, puis faisait évoluer le code davantage pour minimiser cette borne. Ce processus d'auto-amélioration a permis aux chercheurs de trouver des raffinements subtils dans la stratégie d'optimisation qu'une équipe humaine aurait pu négliger. Le résultat de cette évolution automatisée a été une amélioration supplémentaire, poussant la borne jusqu'au nouveau record de 2,371177.

Pour s'assurer que ce résultat n'était pas un artefact dû à des erreurs d'arrondi informatique ou à des imprécisions de virgule flottante, l'équipe a procédé à une étape de vérification rigoureuse. Ils ont pris la solution trouvée par leurs algorithmes et ont converti tous les nombres en fractions exactes, effectuant les calculs finaux avec une précision parfaite. Ils ont également remplacé chaque logarithme dans les équations par une borne rationnelle sûre qui garantissait que les contraintes étaient respectées. Ce processus de certification minutieux a confirmé que la nouvelle borne est mathématiquement valide et exempte du bruit numérique qui affecte souvent de tels calculs complexes.

Les chercheurs notent que bien que leur approche ait produit une meilleure borne, les améliorations deviennent de plus en plus difficiles à obtenir. Les gains réalisés sont comparables à l'ampleur des progrès incrémentiels observés au cours des quarante dernières années. Ils suggèrent que, si de nouvelles améliorations modestes pourraient être possibles en continuant à affiner ces techniques d'optimisation, réaliser un saut beaucoup plus important dans la compréhension de la véritable limite nécessitera probablement des idées mathématiques entièrement nouvelles. Pour l'instant, ce travail témoigne de la puissance de la combinaison des mathématiques théoriques profondes et de la force de calcul de l'apprentissage automatique moderne, prouvant que même dans un domaine doté d'une longue histoire, il reste encore de la place pour la découverte.

Résumé Technique : Amélioration de l'exposant de la multiplication de matrices grâce à l'optimisation moderne et AlphaEvolve

Énoncé du Problème
La complexité computationnelle de la multiplication de matrices, caractérisée par l'exposant $\omega$ où deux matrices $n \times n$ peuvent être multipliées en $O(n^{\omega + o(1)})$ opérations, demeure une question fondamentale ouverte en informatique théorique. Bien que la percée de Strassen en 1969 ait établi $\omega < 2,81$ , la meilleure borne supérieure actuelle est $\omega < 2,371339$ (Alman et al., 2025). Cette borne est dérivée d'un raffinement de la « méthode du laser » connu sous le nom d'analyse de la perte de combinaison (combination loss analysis). Le cœur de cette approche consiste à résoudre un problème d'optimisation non convexe complexe. La difficulté réside dans le compromis entre la complexité de l'optimisation (qui croît de manière doublement exponentielle avec le niveau de récursion $\ell^*$ ) et la précision de la borne résultante. Les résultats de l'état de l'art (SOTA) précédents ont été obtenus avec un niveau de récursion $\ell^* = 3$ , impliquant environ 25 000 paramètres.

Méthodologie
Les auteurs proposent une approche en deux étapes pour améliorer le processus d'optimisation de l'analyse de la perte de combinaison, en ciblant un niveau de récursion plus élevé de $\ell^* = 4$ .

Reformulation et Optimisation Basée sur le Gradient :
- Expansion du Problème : Les auteurs reformulent le problème d'optimisation pour gérer $\ell^* = 4$ . Cela augmente le nombre de paramètres optimisables de ~25k à environ 7 millions.
- Objectif Différentiable : Pour résoudre ce problème non convexe de haute dimension, ils s'éloignent de la programmation quadratique séquentielle (SQP) utilisée dans les travaux précédents. À la place, ils emploient une approche basée sur le gradient.
- Paramétrage : Pour gérer les contraintes selon lesquelles les probabilités doivent être non négatives et leur somme doit être égale à un, les distributions sont paramétrées via des logits et converties à l'aide de la fonction softmax, permettant ainsi une optimisation sans contraintes.
- Gestion de l'Entropie Maximale : Le problème implique le calcul de distributions d'entropie maximale ( $H_{max}$ ) soumises à des contraintes marginales. Plutôt que d'optimiser ces distributions directement, les auteurs utilisent l'algorithme de Sinkhorn-Knopp (issu du transport optimal) pour les calculer. Ils utilisent la différenciation implicite pour rétropropager à travers cet algorithme, garantissant que la fonction objectif reste différentiable et stable.
- Implémentation : L'algorithme est implémenté dans Jax pour tirer parti de la parallélisation matérielle (GPU). Pour gérer la structure de graphe non uniforme de l'arbre d'optimisation, ils introduisent des « nœuds fantômes » avec masquage et regroupent les nœuds en « étapes » spécialisées, permettant de représenter le problème sous forme de tenseurs multidimensionnels pour un traitement parallèle efficace.
Intégration d'AlphaEvolve :
- Les auteurs appliquent AlphaEvolve (Novikov et al., 2025) pour affiner davantage l'algorithme d'optimisation.
- AlphaEvolve modifie le programme d'optimisation lui-même. En utilisant une fonctionnalité de « constructions évolutives », l'algorithme à chaque génération part du meilleur point de solution trouvé par l'algorithme parent, faisant évoluer itérativement le code pour minimiser la borne $\omega$ résultante.
Vérification Rigoureuse :
- Pour garantir l'absence d'erreurs de virgule flottante, les auteurs effectuent une étape de vérification distincte. Ils arrondissent la solution en virgule flottante à des nombres rationnels et réévaluent toutes les quantités dérivées en utilisant l'arithmétique rationnelle exacte.
- Les logarithmes sont remplacés par des bornes rationnelles arrondies dans la direction qui garantit que toutes les contraintes du problème d'optimisation restent satisfaites, fournissant un certificat mathématiquement rigoureux pour la borne.

Contributions Clés et Résultats

Nouvelle Borne Supérieure : L'approche combinée produit une nouvelle borne supérieure de $\omega < 2,371177$ .
Magnitude de l'Amélioration : Cela améliore la SOTA précédente de $\omega < 2,371339$ d'environ $1,62 \times 10^{-4}$ . L'optimisation initiale basée sur le gradient a amélioré la borne de $\approx 0,97 \times 10^{-4}$ , le gain restant étant attribué au raffinement par AlphaEvolve.
Scalabilité : Ce travail démontre la faisabilité de la résolution de problèmes d'analyse de la perte de combinaison à $\ell^* = 4$ , une échelle auparavant intraçable avec les méthodes SQP standards en raison de l'explosion du nombre de paramètres.

Signification et Revendications
L'article affirme que cette amélioration est comparable en magnitude à la plupart des avancées réalisées au cours des 40 dernières années depuis l'établissement de la borne de Coppersmith-Winograd ( $\omega < 2,376$ ). Les auteurs soulignent que leur contribution réside dans l'utilisation de techniques modernes d'apprentissage automatique (descente de gradient, transport optimal et génération de code évolutif) pour résoudre plus efficacement le cadre mathématique existant.

Les auteurs restent modestes quant aux perspectives futures, notant que si de nouvelles améliorations modestes peuvent être réalisables grâce à cette méthodologie axée sur l'optimisation, obtenir des réductions nettement plus importantes de $\omega nécessite probablement de nouvelles idées mathématiques au-delà du cadre actuel de la méthode du laser. Ce travail a été motivé par des discussions au Simons Institute for the Theory of Computing à l'automne 2025.

Articles similaires