⚡ electrical engineering

DeMuon: A Decentralized Muon for Matrix Optimization over Graphs

Cet article introduit DeMuon, la première extension décentralisée de l'optimiseur Muon qui combine l'orthogonalisation de Newton-Schulz avec le suivi de gradient pour atteindre une convergence prouvable et une performance supérieure dans l'optimisation de matrices sur des graphes de communication, particulièrement sous des conditions de bruit à queue lourde.

Auteurs originaux : Chuan He, Shuyi Ren, Jingwei Mao, Erik G. Larsson

Publié 2026-06-03

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Chuan He, Shuyi Ren, Jingwei Mao, Erik G. Larsson

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 un groupe d'amis essayant de résoudre un puzzle géant et complexe ensemble. Ils sont tous dans des pièces différentes (décentralisés) et ne peuvent communiquer qu'avec leurs voisins immédiats. Ils n'ont pas de chef ou de leader central pour leur dire quoi faire ; ils doivent comprendre par eux-mêmes en partageant ce qu'ils voient et en ajustant leurs propres pièces en fonction de ce que leurs voisins leur disent.

Ce document présente une nouvelle façon pour ces amis de résoudre le puzzle plus rapidement et plus précisément. Ils appellent cette nouvelle méthode DeMuon.

Voici la décomposition de son fonctionnement, en utilisant des analogies simples :

Le Problème : Le Puzzle "Matrix"

Dans le monde de l'intelligence artificielle (plus précisément du deep learning), les « pièces du puzzle » ne sont pas seulement des nombres isolés ; ce sont de gigantesques grilles de nombres appelées matrices.

L'ancienne méthode (Vectorisation) : Traditionnellement, les ordinateurs traitaient ces grandes grilles comme de longues listes de nombres plates (vecteurs). C'est comme essayer de résoudre un puzzle 3D en l'aplatissant d'abord en une feuille 2D. Cela fonctionne, mais c'est maladroit et cela ignore la forme des pièces.
La nouvelle méthode (Muon) : Une méthode récente appelée Muon a réalisé que traiter les pièces selon leur forme 3D naturelle est bien meilleur. Elle utilise une « boussole » spéciale (appelée norme spectrale) pour décider de la direction dans laquelle déplacer les pièces. Cela fonctionne extrêmement bien lorsque tout le monde est dans la même pièce (centralisé).

Le Défi : Devenir Décentralisé

Les auteurs se sont demandé : Pouvons-nous utiliser cette boussole intelligente "Muon" quand nos amis sont dans des pièces différentes et ne peuvent pas parler à un chef central ?
C'est difficile car :

Vues différentes : Chaque ami voit une partie légèrement différente du puzzle (données locales).
Pas de chef : Ils ne peuvent pas simplement demander à un leader : « Quel est le meilleur mouvement ? ». Ils doivent deviner le meilleur mouvement « global » en écoutant leurs voisins.
Confusion : S'ils ne font pas attention, ils pourraient tous commencer à bouger dans des directions différentes, et le puzzle ne sera jamais résolu.

La Solution : DeMuon

Le papier propose DeMuon, une méthode qui permet aux amis de résoudre le puzzle ensemble sans chef. Elle combine deux astuces principales :

1. La « Boussole Partagée » (Gradient Tracking)
Imaginez que chaque ami possède une boussole. Parce qu'ils sont dans des pièces différentes, leurs boussoles pointent dans des directions légèrement différentes.

Anciennes méthodes décentralisées : Les amis pointaient simplement leurs boussoles vers leurs voisins et espéraient qu'elles s'alignent.
L'astuce de DeMuon : Ils utilisent une technique appelée gradient tracking (suivi du gradient). C'est comme une course de relais où chaque ami ne transmet pas seulement sa direction actuelle, mais transmet aussi une « note de correction » sur la façon dont sa direction a changé depuis la dernière étape. Cela aide tout le groupe à s'accorder sur la véritable direction globale, même s'ils sont éloignés les uns des autres.

2. L'« Orthogonalisation de Matrice » (La Magie de Muon)
Lorsqu'un ami décide de déplacer sa pièce de puzzle, il ne la pousse pas au hasard. Il utilise la technique Muon, qui est comme un « changeur de forme » spécialisé.

Au lieu de simplement pousser la pièce vers l'avant, Muon vérifie la « forme » de la pièce (en utilisant la norme spectrale) et la fait pivoter pour qu'elle soit parfaitement alignée avant de la déplacer.
Pensez à un danseur qui ne se contente pas de marcher vers l'avant, mais qui prend d'abord une pose parfaite pour s'assurer qu'il est équilibré. Cela empêche les pièces du puzzle de rester « bloquées » ou de bouger de manière inefficace.

La Version Survitaminée : DeMuon-A

Les auteurs ont également créé une version encore plus rapide appelée DeMuon-A.

L'analogie : Si DeMuon est un coureur qui regarde le sol et fait un pas, DeMuon-A est un coureur qui regarde le sol, prédit où il sera dans deux étapes, et fait ensuite un grand bond basé sur cette prédiction.
Comment ça marche : Elle utilise une technique de multi-extrapolation. Elle demande : « Si je continue de cette façon, où serai-je ? » et utilise cette prédiction pour faire un pas plus grand et plus intelligent. Cela nécessite que le puzzle soit « lisse » (prévisible), mais quand cela fonctionne, cela converge vers la solution beaucoup plus vite.

Qu'ont-ils prouvé ?

Les auteurs ont fait deux choses principales :

Preuve Mathématique : Ils ont utilisé des mathématiques avancées pour prouver que si les amis suivent ces règles, ils finiront par s'accorder sur la solution (consensus) et trouveront le meilleur arrangement possible des pièces du puzzle (stationnarité). Ils ont prouvé que cela fonctionne même si les amis sont dans un réseau désordonné (certains peuvent parler à beaucoup de personnes, d'autres à peu).
Test en conditions réelles : Ils ont testé cela sur l'entraînement d'un modèle de langage (un type d'IA qui écrit du texte).
- Ils ont configuré 8 ordinateurs (nœuds) connectés de différentes manières (comme un cercle parfait, un anneau ou une toile désordonnée).
- Résultat : DeMuon et DeMuon-A ont appris la tâche de langage bien mieux et plus rapidement que les méthodes standards (comme DSGD). Ils ont atteint un score d'erreur plus bas, ce qui signifie que l'IA est plus intelligente.

Résumé

DeMuon est une nouvelle façon pour un groupe d'ordinateurs d'entraîner des modèles d'IA ensemble sans chef central.
Il conserve le « changement de forme intelligent » (optimisation de matrice) de la méthode Muon originale.
Il ajoute un système de « course de relais » (gradient tracking) pour que tout le monde s'accorde sur la direction.
DeMuon-A ajoute un « bond de prédiction » pour aller encore plus vite.
Le papier prouve mathématiquement que cela fonctionne et montre, par des expériences, que cela surpasse les méthodes actuelles en termes de vitesse et de précision.

Le papier ne prétend pas que ceci est destiné à un usage médical ou à des applications futures spécifiques ; il concerne strictement l'amélioration de l'efficacité mathématique de l'entraînement de modèles d'IA dans un réseau décentralisé.

Résumé Technique : DeMuon - Un Muon Décentralisé pour l'Optimisation de Matrices sur Graphes

Énoncé du Problème

Cet article traite du problème de l'optimisation de matrices entièrement décentralisée sur des graphes de communication. L'objectif est de résoudre le problème d'optimisation multi-agents suivant :
$\min_{X \in \mathbb{R}^{m \times n}} f(X) := \frac{1}{N} \sum_{i=1}^N f_i(X)$
où $N$ agents sont connectés via un graphe dirigé $\mathcal{G}=(\mathcal{V}, \mathcal{E})$ , et chaque nœud $i$ détient une fonction objectif locale $f_i$ . Contra\à l'optimisation décentralisée traditionnelle qui vectorise souvent les variables matricielles, ce travail se concentre sur la préservation de la structure de la matrice, en exploitant spécifiquement les techniques de l'algorithme centralisé Muon (Jordan et al., 2024). L'objectif est d'atteindre une convergence globale et un consensus entre les agents sans serveur central, tout en atténuant l'hétérogénéité des fonctions objectifs locales.

Méthodologie

Le papier propose deux algorithmes : DeMuon (une variante décentralisée de Muon) et DeMuon-A (une variante accélérée).

1. DeMuon : Muon Décentralisé

DeMuon intègre des mises à jour basées sur la norme spectrale dans un cadre de suivi de gradient (gradient-tracking). L'algorithme maintient trois séquences : des estimateurs de gradient locaux $\{M^{(k)}\}$ , des estimateurs de gradient globaux $\{V^{(k)}\}$ , et des itérés locaux $\{X^{(k)}\}$ .

Moment Local : Chaque nœud met à jour son estimateur local $M^{(k)}_i$ en utilisant une moyenne mobile exponentielle des gradients stochastiques.
Suivi de Gradient : Les nœuds mettent à jour $V^{(k)}_i$ en agrégeant les informations de leurs voisins pour suivre le gradient global, assurant ainsi un consensus sur la direction du gradient malgré l'hétérogénéité locale.
Orthogonalisation de Matrice : L'itéré local $X^{(k+1)}_i$ est mis à jour en agrégeant les mises à jour des voisins, en appliquant spécifiquement une fonction de signe de matrice ( $\text{msgn}(\cdot)$ ) au gradient suivi. Cette étape résout un sous-problème linéaire contraint par la norme en utilisant la norme spectrale ( $\|\cdot\|$ ), ce qui est central à la méthodologie Muon.

Garanties Théoriques pour DeMuon :
Sous des hypothèses de bruit borné et de continuité de Lipschitz du gradient par rapport aux normes spectrale et nucléaire, les auteurs établissent :

Erreur de Consensus : L'erreur $\|X^{(k)} - \mathbf{1} \otimes \bar{X}^{(k)}\|$ est bornée par $O(\frac{\sqrt{N}\lambda \eta}{1-\lambda})$ , où $\lambda$ caractérise le taux de mélange du graphe.
Erreur de Stationnarité : L'erreur de stationnarité moyenne converge à une vitesse de $O(K^{-1/4})$ avec un pas $\eta$ et un momentum $\theta$ correctement ajustés. Cela correspond au taux de convergence optimal de la SGD normalisée avec momentum en mode centralisé.

2. DeMuon-A : Muon Décentralisé Accéléré

DeMuon-A étend la technique de multi-extrapolation (He et al., 2026b) au cadre matriciel décentralisé.

Mécanisme : Il effectue $q = p-1$ étapes d'extrapolation locale par itération pour générer des points $Z^{(k,s)}_i$ , exploitant la lissité d'ordre supérieur de la fonction objectif.
Hypothèses : Il nécessite une condition de Lipschitz d'ordre supérieur sur la $p$ -ième dérivée des fonctions $f_i$ , induite par les normes spectrale et nucléaire.
Convergence : Sous ces conditions, DeMuon-A atteint un taux d'erreur de stationnarité amélioré de $O(K^{-p/(3p+1)})$ et un taux d'erreur de consensus de $O(K^{-(2p+1)/(3p+1)})$ .

Contributions Clés

Proposition Algorithmique : Les auteurs introduisent DeMuon, le premier algorithme d'optimisation de matrice entièrement décentralisé qui incorpore l'orthogonalisation basée sur la norme spectrale de Muon et le suivi de gradient.
Analyse de Convergence : Ils fournissent des garanties de convergence globale rigoureuses pour DeMuon et DeMuon-A en termes d'erreurs de stationnarité et de consensus. Notamment, l'analyse repose sur les inégalités de moments de martingales de matrices pour établir une convergence indépendante de la dimension (dimension-free).
Accélération : Le papier propose DeMuon-A, qui intègre la multi-extrapolation pour exploiter la lissité d'ordre supérieur, offrant des taux de convergence améliorés par rapport à l'algorithme de base DeMuon.
Validation Empirique : Des expériences numériques sur l'apprentissage profond distribué (entraînement de Transformers) et la régression de matrice distribuée démontrent les avantages pratiques des méthodes proposées par rapport aux bases décentralisées existantes.

Résultats Expérimentaux

Les auteurs ont évalué DeMuon par rapport à trois bases : DSGD (SGD décentralisé classique), DSGD-C (SGD avec écrêtage) et DSGD-N (SGD normalisé avec suivi de gradient).

Configuration : Les expériences ont été menées sur un modèle GPT de 7,4 millions de paramètres entraîné sur le jeu de données Multi30k à travers trois topologies de graphes : Complète, Exponentielle Dirigée et en Anneau.
Performance : DeMuon surpasse systématiquement toutes les bases en termes de perte d'entraînement, de perte de validation et de perplexité à travers toutes les topologies.
Consensus : L'erreur de consensus pour DeMuon est restée compétitive ou inférieure à celle des bases, indiquant un accord efficace entre les agents.
Détails : Dans la topologie de Graphe Complet, DeMuon a atteint une perte de validation finale de 0,240 (perplexité 1,27), nettement inférieure à celle de DSGD-N (0,302) et DSGD (7,031).

Signification et Revendications

Le papier affirme que DeMuon comble avec succès le fossé entre le succès empirique de Muon dans l'apprentissage profond centralisé et les exigences de l'optimisation décentralisée.

Convergence Indépendante de la Dimension : Contra \à certains travaux récents (ex. Zhang et al., 2026a) qui peuvent dépendre explicitement de la dimensionnalité du problème, les auteurs affirment que leur utilisation des inégalités de moments de martingales de matrices permet des garanties de convergence qui ne dépendent pas explicitement des dimensions de la matrice $(m, n)$ .
Avantage Pratique : Les résultats suggèrent que la structure spécifique de Muon (contraintes de norme spectrale et orthogonalisation de matrice) offre des avantages pratiques clairs dans les context d'optimisation décentralisée, particulièrement pour l'entraînement de grands modèles de langage où les structures matricielles sont inhérentes.
Rigueur Théorique : Ce travail établit que les bénéfices du momentum et de la normalisation dans l'optimisation de matrices peuvent être préservés dans un environnement entièrement décentralisé sans coordinateur central, à condition d'utiliser le suivi de gradient et des mises à jour appropriées basées sur les normes.

Les auteurs positionnent ce travail comme une étape vers l'apport de techniques d'optimisation de matrice avancées au monde décentralisé, motivé par des applications dans l'apprentissage profond distribué et des problèmes classiques comme l'ACP distribuée et la complétion de matrice.