Resumo Técnico: Decomposição de Dependência de Baixo Posto via Fatoração de Matriz Não Negativa Simétrica Acelerada

Declaração do Problema

A Fatoração de Matriz Não Negativa Simétrica (SymNMF) busca decompor uma matriz de dependência simétrica e de entradas não negativas $S \in \mathbb{R}^{n \times n}_+$ em um fator de baixo posto $H \in \mathbb{R}^{n \times k}_+$ (onde $k \ll n$) tal que $S \approx HH^\top$. Esta decomposição revela estruturas de grupos latentes onde os membros compartilham padrões de dependência comuns, servindo tanto como agrupamento suave (soft clustering) quanto como embeddings aprendidos.

O artigo aborda a lacuna de escalabilidade da SymNMF. Embora o método seja bem estabelecido, sua implementação prática em portfólios de larga escala (milhares a milhões de instrumentos) tem sido dificultada por:

1. Restrições de Memória: A formulação do objetivo padrão exige matrizes intermediárias explícitas de $n \times n$, limitando trabalhos anteriores a tamanhos moderados ($n \lesssim 10^4$).
2. Falta de Comparação Sistemática: Não há uma avaliação abrangente de famílias de solvers em entradas de verdade fundamental (ground-truth) realistas e controladas em escala.
3. Desafios de Otimização: Métodos eficazes em escalas moderadas frequentemente falham nas execuções longas exigidas para $n$ grande, particularmente devido à interação entre o tratamento de restrições (projeção vs. reparametrização) e a memória do otimizador adaptativo.

O estudo foca em dois tipos específicos de entradas que representam fatores de risco financeiro:

• Matrizes de Correlação de Pearson Absoluta: Capturando a dependência através de toda a distribuição.
• Matrizes de Dependência de Cauda Pareada (TPDM): Fundamentadas na Teoria de Valor Extremo, capturando a dependência condicional a eventos extremos. Estas matrizes frequentemente exibem um espectro "plano" e mal condicionado, dominado por um único fator comum.

Metodologia

1. Reformulação Eficiente de Memória

Para permitir a escalabilidade até $n \approx 10^6$, os autores reformulam a função objetivo usando uma identidade de traço. A norma de Frobenius padrão $\|S - HH^\top\|_F^2$ é expandida para:
$$\|S\|_F^2 - 2 \text{tr}(H^\top SH) + \|H^\top H\|_F^2$$
Isso elimina a necessidade de formar a matriz residual $n \times n$ de $S - HH^\top$. Todos os intermediários são reduzidos para matrizes $n \times k$ ou $k \times k$. Esta mudança algébrica aproximadamente dobra o $n$ máximo viável em uma única GPU (de $\sim 60.000$ para $\sim 130.000$ em FP32) e permite a distribuição multi-nó para $n = 10^6$.

2. Famílias de Solvers e Configurações

O estudo avalia sete famílias de algoritmos (mais de 30 configurações) através de três paradigmas:

• Projeção de Gradiente: Gradiente Projetado (PGD), Gradiente Proximal Acelerado (APG/FISTA).
• Ordem Superior Adaptativa: AdaGrad, RMSprop, Adam, NAdam, Adan, e três extensões inovadoras introduzidas neste trabalho:
  • AdaGrad em Partes (Piecewise AdaGrad): Reinicia o acumulador ao estagnar o objetivo para evitar a saturação.
  • SVRG Estocástico por Linha: Combina subamostragem de linhas com snapshots periódicos de gradiente total para manter o crescimento uniforme do acumulador.
  • Block-SVRG AdaptGrow: Utiliza amostragem de blocos densos com crescimento de lote adaptativo (começando pequeno, crescendo para lote total ao estagnar) e snapshots híbridos de SVRG para corrigir a heterogeneidade do acumulador por linha.
• Divisão/Gradiente de Espelho: Atualizações Multiplicativas (MU), ADMM, Descida de Coordenadas em Blocos (HALS, ANLS) e Desdobramento Profundo (SymNMF-Net).

3. Tratamento de Restrições

O artigo compara duas estratégias para impor $H \ge 0$:

• Espaço Projetado: Clamping direto de $H$ após as atualizações.
• Reparametrização Softplus (Espaço Logarítmico): Otimização de um $\Theta$ sem restrições onde $H = \text{softplus}(\Theta)$.
  Os autores descobrem que o Softplus auxilia otimizadores de memória curta (ex: RMSprop) e métodos de segunda ordem em pequenas escalas, mas corrompe acumuladores de memória longa (ex: AdaGrad, Adam) conforme as execuções se alongam, devido à natureza não estacionária do gradiente da regra da cadeia. Consequentemente, experimentos de larga escala utilizam o espaço projetado.

4. Critérios de Convergência

Uma regra de parada rigorosa de três partes é aplicada uniformemente:

1. Portão de Perda (Loss Gate): Erro quadrático normalizado $E_t < 0.1$.
2. Condição KKT: Norma do gradiente projetado normalizada por entrada $\|\nabla_{\text{proj}} f(H)\|_F / (nk) < \tau_g$.
3. Estagnação: Melhoria relativa do objetivo abaixo de um limite.
   Isso garante que as soluções não sejam apenas de baixo erro, mas também pontos estacionários, evitando convergência falsa em vales planos.

Principais Resultados

Fase 1: Seleção de Algoritmo ($n \le 10^4$)

Em uma única GPU NVIDIA GB200, onze métodos convergiram de forma confiável. No entanto, apenas seis atenderam aos limiares estritos de eficiência (convergência em $<4$ segundos em $n=10^4$):

• ADMM
• RMSprop
• Block-SVRG AdaptGrow
• AdaGrad
• Row-Stochastic SVRG
• Piecewise AdaGrad

Atualizações multiplicativas, PGD padrão e desdobramento profundo falharam em convergir ou foram significativamente mais lentos. Métodos de segunda ordem (L-BFGS, Newton) falharam nos espectros de TPDM devido à má aproximação de curvatura ou problemas de memória.

Fase 2: Viabilidade de Larga Escala ($n = 10^5, 10^6$)

Os seis métodos selecionados foram testados em clusters de GPU multi-nó (até 64 GPUs).

• Dominância da Família AdaGrad: Cinco métodos da família AdaGrad (AdaGrad, Piecewise, Row-Stoch SVRG, Block-SVRG AdaptGrow, RMSprop) convergiram com sucesso em $n=10^6$. O ADMM foi omitido nesta escala devido à velocidade.
• Dependência Espectral: O solver "mais rápido" depende da matriz espectral:
  • Matrizes de Correlação (Espectro de Baixo Posto Dominante): O AdaGrad de lote total (full-batch) é o mais rápido. O problema possui um hiato claro entre sinal e ruído, permitindo execuções curtas onde passos de lote total são eficientes.
  • TPDM (Espectro Plano e Mal Condicionado): O Block-SVRG AdaptGrow é o mais rápido. O espectro é dominado por um fator comum com hiatos próximos de zero, exigendo execuções longas. O menor custo por iteração da estratégia de amostragem de bloco adaptativa supera a necessidade de mais iterações.
• Desempenho: Em $n=10^6$, o Block-SVRG AdaptGrow resolveu TPDM em ~4 minutos (409 iterações), enquanto o AdaGrad resolveu correlação em ~2 minutos (72 iterações).

Baseline de Agrupamento

O artigo compara o K-means Esférico (aplicado às linhas de $S$) como uma alternativa de rótulo rígido (hard-label).

• Eficiência: O K-means é significativamente mais rápido (menos iterações) quando existe uma estrutura de agrupamento angular.
• Degenerescência: O K-means falha (silhueta $\approx 0$) quando a matriz colapsa em direção a um único fator comum (baixo posto efetivo, $r_{\text{eff}} \to 1$), um regime comum em grandes TPDMs. Nestes casos, a fatoração suave fornecida pela SymNMF permanece necessária.

Significância e Alegações

O artigo afirma preencher a lacuna entre a SymNMF teórica e a aplicação prática de larga escala na estimativa de risco financeiro. Suas principais contribuições são:

1. Escalabilidade: Demonstrar que a SymNMF densa é tratável até $n=10^6$ via reformulação de identidade de traço e distribuição multi-GPU, removendo o gargalo de memória $O(n^2)$.
2. Recomendações de Solver: Fornecer um guia baseado em dados para a seleção de solvers com base no tipo de entrada e escala. Identifica o AdaGrad diagonal como o padrão para execuções curtas e o Block-SVRG AdaptGrow para execuções longas e mal condicionadas.
3. Inovação Algorítmica: Introduzir e validar extensões de engenharia específicas (Piecewise AdaGrad, Block-SVRG AdaptGrow) que resolvem a tensão entre a memória infinita do AdaGrad (boa para objetivos estacionários) e a saturação em execuções longas.
4. Tratamento de Restrições: Caracterizar o compromisso dependente de escala entre projeção e Softplus, aconselhando contra o uso de Softplus para métodos adaptativos de memória longa em larga escala.

Os autores enfatizam que estas descobertas são propriedades do próprio cenário de otimização da SymNMF, tornando-as aplicáveis a qualquer problema com características espectrais semelhantes, não apenas aos inputs financeiros específicos utilizados.