Riemannian Optimization for Hadamard Products of Low-Rank Matrices

Resumo Técnico: Otimização Riemanniana para Produtos de Hadamard de Matrizes de Baixo Posto

Formulação do Problema
O artigo aborda o desafio de modelar dados com estrutura multiplicativa usando o produto elemento a elemento (Hadamard) de duas matrizes de baixo posto. A matriz alvo $W \in \mathbb{R}^{m \times n}$ é modelada como:
$$W = (GH^\top) \circ (UV^\top)$$
onde $G, U \in \mathbb{R}^{m \times r_1, r_2}$ e $H, V \in \mathbb{R}^{n \times r_1, r_2}$. Embora esta formulação ofereça eficiência de parâmetros em comparação com uma fatoração padrão de posto-$r_1r_2$ (exigindo $(m+n)(r_1+r_2)$ parâmetros versus $(m+n)r_1r_2$), ela introduz um cenário de otimização complexo. Especificamente, o modelo exibe simetrias que vão além da reparametrização invariante de General Linear (GL) padrão. O produto $W$ permanece invariante sob escalonamentos acoplados de linhas e colunas entre os dois pares de fatores $(G, H)$ e $(U, V)$. Esses graus de liberdade adicionais criam uma geometria desafiadora que os métodos de gradiente descendente euclidiano padrão têm dificuldade em navegar eficientemente.

Os solvers existentes enfrentam limitações: o Gradiente Descendente Alternado (AGD) ignora a geometria específica e as simetrias de escala, enquanto o Descendente de Coordenadas em Blocos (BCD) é altamente eficaz para perdas de mínimos quadrados, mas carece de soluções em forma fechada para perdas não quadráticas (ex: predição de ligação logística ou entropia cruzada), limitando sua aplicabilidade em estatística robusta e outros domínios.

Metodologia
Os autores propõem formular o problema de aprendizado como uma tarefa de otimização em um variedade de quociente Riemanniana. Esta abordagem considera explicitamente as invariâncias naturais do produto de Hadamard.

1. Geometria da Variedade: Os autores definem a variedade de quociente $\mathcal{M}$ fatorando o grupo de simetria completo $\mathcal{G}$, que inclui:

   • Invariância de reparametrização GL padrão para cada par de fatores.
   • Novas simetrias de escala de cross-Hadamard, onde matrizes diagonais invertíveis escalonam linhas e colunas entre os dois pares de fatores inversamente.
     A variedade é construída a partir do espaço de matrizes de posto de coluna total módulo esta ação de grupo.

2. Métrica Riemanniana Inovadora: Uma contribuição crítica é a derivação de uma métrica Riemanniana em bloco-diagonal ($g_x$) derivada do pullback do produto interno de Frobenius.

   • A métrica de pullback completa acopla todos os quatro blocos de fatores, resultando em um sistema linear denso e computacionalmente caro.
   • A métrica proposta retém apenas os blocos diagonais do pullback, descartando termos cruzados.
   • A métrica é definida via matrizes de peso ($S$-blocos) para cada linha/coluna dos fatores. Por exemplo, o peso para a $i$-ésima linha de $G$ é $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$, onde $Y = UV^\top$.
   • Invariância: A métrica é provada ser invariante tanto sob a reparametrização GL quanto sob as simetrias de escala de cross-Hadamard. Isso garante que o otimizador seja insensível à divisão arbitrária de magnitude entre os fatores.
   • Conexão com BCD: As matrizes de peso na métrica proposta correspondem exatamente às matrizes de equações normais usadas nas atualizações de BCD. Assim, o gradiente Riemanniano pode ser interpretado como a execução de um passo de BCD "suave" simultaneamente em todas as linhas para quaisquer funções de perda suaves.

3. Algoritmo de Otimização (RGD): Os autores desenvolvem um algoritmo de Gradiente Descendente Riemanniano (RGD):

   • Computação do Gradiente: O gradiente Riemanniano é computado resolvendo sistemas lineares independentes de $r \times r$ (um por linha/coluna) usando os $S$-blocos.
   • Tamanho do Passo: Um tamanho de passo de Cauchy de Gauss–Newton livre de ajuste (tuning-free) é derivado. Este tamanho de passo é invariante sob o grupo de simetria e não requer ajuste de hiperparâmetros.
   • Retração: Uma retração aditiva é usada para mapear as atualizações de volta para a variedade.
   • Complexidade: O custo por iteração escala linearmente com o número de entradas observadas $N$ ($O(Nr)$) e polinomialmente com os postos ($O((m+n)r^4)$), tornando-o eficiente para grandes conjuntos de dados.

Principais Contribuições

1. Caracterização Geométrica: Descrição formal da estrutura de variedade de quociente para produtos de Hadamard, identificando as simetrias de escala GL e de cross-Hadamard.
2. Métrica Invariante de Escala: Proposta de uma nova métrica Riemanniana em bloco-diagonal que respeita o grupo de simetria completo e desacopla a otimização em subproblemas independentes de linha/coluna.
3. Desenvolvimento de Algoritmo: Derivação de um algoritmo RGD com um tamanho de passo de Gauss–Newton livre de ajuste que suporta qualquer função de perda suave, ao contrário do BCD que é restrito a mínimos quadrados.
4. Validação Empírica: Demonstração de que o método atinge desempenho comparável ao BCD em tarefas de mínimos quadrados, enquanto supera o BCD em objetivos não quadráticos e alcança resultados superiores em configurações específicas de posto de Hadamard.

Resultados Experimentais
Os autores avaliaram o RGD em conjuntos de dados sintéticos e do mundo real:

• Testes de Estresse Sintéticos: Em alvos sintéticos de $2.000 \times 1.000$, o RGD demonstrou:
  • Invariância de Escala: O erro de recuperação permaneceu constante através de variações de separação de escala diagonal ($\kappa_{scale}$), verificando empiricamente a propriedade de invariância da métrica. Em contraste, o AGD mostrou sensibilidade à escala.
  • Condicionamento: O RGD performou comparavelmente ao BCD através de variações nos números de condição dos fatores, superando significativamente o AGD.
  • Robustez ao Ruído: O RGD convergiu para o nível de ruído na mesma taxa que o BCD, enquanto o AGD ficou para trás.
• Conjuntos de Dados do Mundo Real:
  • Aproximação de Matriz Completa: Nos datasets Camera, Football e Les Misérables, o RGD acompanhou de perto o BCD em erro relativo, confirmando que a métrica fornece pré-condicionamento equivalente ao BCD para perdas quadráticas.
  • MovieLens-1M: Em uma tarefa de completagem de matriz com um orçamento de parâmetros fixo ($r_1+r_2=6$), o RGD alcançou o menor RMSE de teste entre todas as configurações de posto de Hadamard testadas. Notavelmente, a configuração equilibrada $(3,3)$ superou a quase-vanilla $(1,5)$, sugerindo que a capacidade de interação de Hadamard ($r_1r_2$) contribui para a precisão. O RGD consistentemente superou o AGD e alcançou um RMSE menor que o BCD em configurações genuinamente de Hadamard.

Significância e Alegações
O artigo afirma preencher a lacuna entre a eficiência do BCD para problemas de mínimos quadrados e a flexibilidade dos métodos baseados em gradiente para perdas suaves gerais. Ao elevar o problema para uma variedade de quociente Riemanniana, os autores fornecem um framework principiado que lida com as simetrias complexas do produto de Hadamard. O algoritmo RGD proposto oferece um método de otimização livre de ajuste e invariante de escala que escala linearmente com o tamanho dos dados. Os autores afirmam que este framework se estende naturalmente para produtos de $k$ matrizes de baixo posto e é compatível com outros solvers Riemannianos (ex: gradientes conjugados, métodos de região de confiança), oferecendo uma alternativa robusta aos solvers existentes para modelagem de baixo posto multiplicativo.