Resumo Técnico: DeMuon - Um Muon Descentralizado para Otimização de Matrizes sobre Grafos

Declaração do Problema

Este artigo aborda o problema da otimização de matrizes totalmente descentralizada sobre grafos de comunicação. O objetivo é resolver o problema de otimização multiagente:
$$\min_{X \in \mathbb{R}^{m \times n}} f(X) := \frac{1}{N} \sum_{i=1}^N f_i(X)$$
onde $N$ agentes estão conectados via um grafo direcionado $\mathcal{G}=(\mathcal{V}, \mathcal{E})$, e cada nó $i$ detém uma função objetivo local $f_i$. Diferente dos métodos tradicionais de otimização descentralizada que frequentemente vetorizam variáveis matriciais, este trabalho foca em preservar a estrutura da matriz, especificamente aproveitando técnicas do algoritmo centralizado Muon (Jordan et al., 2024). O objetivo é alcançar convergência global e consenso entre os agentes sem um servidor central, enquanto mitiga a heterogeneidade nas funções objetivas locais.

Metodologia

O artigo propõe dois algoritmos: DeMuon (uma variante descentralizada do Muon) e DeMuon-A (uma variante acelerada).

1. DeMuon: Muon Descentralizado

O DeMuon integra atualizações baseadas na norma espectral em um framework de rastreamento de gradiente (gradient-tracking). O algoritmo mantém três sequências: estimadores de gradiente local $\{M^{(k)}\}$, estimadores de gradiente global $\{V^{(k)}\}$ e iterados locais $\{X^{(k)}\}$.

• Momento Local: Cada nó atualiza seu estimador local $M^{(k)}_i$ usando uma média móvel exponencialmente ponderada de gradientes estocásticos.
• Rastreamento de Gradiente: Os nós atualizam $V^{(k)}_i$ agregando informações de vizinhos para rastrear o gradiente global, garantindo o consenso na direção do gradiente apesar da heterogeneidade local.
• Ortogonalização de Matriz: O iterado local $X^{(k+1)}_i$ é atualizado agregando as atualizações dos vizinhos, aplicando especificamente uma função de sinal de matriz ($\text{msgn}(\cdot)$) ao gradiente rastreado. Esta etapa resolve um subproblema linear com restrição de norma usando a norma espectral ($\|\cdot\|$), que é central à metodologia Muon.

Garantias Teóricas para o DeMuon:
Sob suposições de ruído limitado e continuidade Lipschitz do gradiente em relação às normas espectral e nuclear, os autores estabelecem:

• Erro de Consenso: O erro $\|X^{(k)} - \mathbf{1} \otimes \bar{X}^{(k)}\|$ é limitado por $O(\frac{\sqrt{N}\lambda \eta}{1-\lambda})$, onde $\lambda$ caracteriza a taxa de mistura do grafo.
• Erro de Estacionariedade: O erro de estacionariedade médio converge a uma taxa de $O(K^{-1/4})$ com tamanho de passo $\eta$ e momento $\theta$ devidamente ajustados. Isso corresponde à taxa de convergência ótima do SGD normalizado centralizado com momento.

2. DeMuon-A: Muon Descentralizado Acelerado

O DeMuon-A estende a técnica de multi-extrapolação (He et al., 2026b) para o cenário de matriz descentralizada.

• Mecanismo: Ele realiza $q = p-1$ etapas de extrapolação local por iteração para gerar pontos $Z^{(k,s)}_i$, explorando a suavidade de ordem superior da função objetivo.
• Suposições: Requer uma condição Lipschitz de ordem superior na $p$-ésima derivada das funções $f_i$, induzida pelas normas espectral e nuclear.
• Convergência: Sob estas condições, o DeMuon-A alcança uma taxa de erro de estacionariedade melhorada de $O(K^{-p/(3p+1)})$ e uma taxa de erro de consenso de $O(K^{-(2p+1)/(3p+1)})$.

Principais Contribuições

1. Proposta Algorítmica: Os autores introduzem o DeMuon, o primeiro método de otimização de matriz totalmente descentralizado que incorpora a ortogonalização baseada em norma espectral e o rastreamento de gradiente do Muon.
2. Análise de Convergência: Eles fornecem garantias rigorosas de convergência global tanto para o DeMuon quanto para o DeMuon-A em termos de erros de estacionariedade e consenso. Notavelmente, a análise depende de desigualdades de momento de martingales de matriz para estabelecer uma convergência independente da dimensão (dimension-free).
3. Aceleração: O artigo propõe o DeMuon-A, que integra multi-extrapolação para aproveitar a suavidade de ordem superior, oferecendo taxas de convergência melhoradas sobre o algoritmo base DeMuon.
4. Validação Empírica: Experimentos numéricos em aprendizado profundo distribuído (treinamento de Transformer) e regressão de matrizes distribuída demonstram as vantagens práticas dos métodos propostos sobre as linhas de base descentralizadas existentes.

Resultados Experimentais

Os autores avaliaram o DeMuon contra três baselines: DSGD (vanilla decentralized SGD), DSGD-C (clipped SGD) e DSGD-N (normalized SGD com rastreamento de gradiente).

• Configuração: Os experimentos foram conduzidos em um modelo GPT de 7.4M de parâmetros treinado no dataset Multi30k através de três topologias de grafo: Completo, Exponencial Direcionado e Anel (Ring).
• Desempenho: O DeMuon superou consistentemente todos os baselines em termos de perda de treinamento, perda de validação e perplexidade em todas as topologias.
• Consenso: O erro de consenso para o DeMuon permaneceu competitivo ou inferior aos baselines, indicando um acordo eficaz entre os agentes.
• Especificidades: Na topologia de Grafo Completo, o DeMuon alcançou uma perda de validação final de 0.240 (perplexidade 1.27), significativamente menor que o DSGD-N (0.302) e o DSGD (7.031).

Significância e Alegações

O artigo afirma que o DeMuon consegue unir com sucesso o sucesso empírico do Muon no aprendizado profundo centralizado com os requisitos da otimização descentralizada.

• Convergência Independente da Dimensão: Ao contrário de alguns trabalhos recentes (ex: Zhang et al., 2026a) que podem depender explicitamente da dimensionalidade do problema, os autores afirmam que o uso de desigualdades de momento de martingales de matriz permite garantias de convergência que não dependem explicitamente das dimensões da matriz $(m, n)$.
• Vantagem Prática: Os resultados sugerem que a estrutura específica do Muon (restrições de norma espectral e ortogonalização de matriz) proporciona vantagens práticas claras em cenários descentralizados, particularmente para o treinamento de grandes modelos de linguagem onde estruturas de matriz são inerentes.
• Rigor Teórico: O trabalho estabelece que os benefícios do momento e da normalização na otimização de matriz podem ser preservados em um ambiente totalmente descentralizado sem um coordenador central, desde que o rastreamento de gradiente e as atualizações apropriadas baseadas em norma sejam utilizados.

Os autores posicionam este trabalho como um passo para levar técnicas avançadas de otimização de matriz ao mundo descentralizado, motivados por aplicações em aprendizado profundo distribuído e problemas clássicos como PCA distribuído e completude de matriz.