Variational Free Energy Pivot Selection for Pivoted Cholesky

Resumo Técnico: Seleção de Pivô por Energia Livre Variacional para Cholesky Pivotado

Definição do Problema
Aproximações de baixo posto de matrizes definidas positivas simétricas (SPD) são fundamentais na álgebra linear numérica, particularmente na regressão de Processos Gaussianos (GP), onde a matriz de kernel $K$ é aproximada por uma fatoração de posto-$r$ $\tilde{K} = LL^\top$. Métodos clássicos, como o Cholesky com pivoteamento guloso e aleatório (RPCholesky), selecionam pivôs sequencialmente para minimizar o erro da norma de traço algébrico do resíduo ($\text{tr}(K - \tilde{K})$). No entanto, em muitas aplicações, a matriz $K$ não é avaliada isoladamente, mas dentro de um funcional de matriz não linear. Especificamente, na regressão de GP, a qualidade da aproximação é determinada pela Energia Livre Variacional (VFE), denotada por $L(\tilde{K})$, que serve como um limite inferior para a log-verossimilhança marginal.

O funcional VFE combina três termos distintos: um termo de log-determinante (complexidade), um termo quadrático de ajuste de dados e um termo de penalidade de traço. As regras de seleção de pivô existentes, que dependem apenas das magnitudes diagonais do resíduo, visam apenas o erro da norma de traço. Consequentemente, elas negligenciam os componentes de log-determinante e de ajuste de dados, podendo levar a aproximações sistematicamente subótimas para o objetivo de inferência específico. O artigo aborda a seguinte questão: Como deve ser realizada a seleção de pivôs quando o objetivo é otimizar um funcional de matriz em vez de um erro de aproximação puramente algébrico?

Metodologia
Os autores propõem uma nova regra de seleção de pivô, denominada Cholesky pivotado $\Delta$-VFE, que maximiza diretamente a mudança exata de um passo na funcional VFE sob atualizações de posto-1 consistentes com Cholesky.

1. Derivação da Fórmula de Ganho:
   Os autores derivam uma expressão de forma fechada para a mudança exata $\Delta L$ na VFE $L(\tilde{K})$ induzida por uma atualização de posto-1 $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$. Usando o Lema do Determinante de Matriz e a fórmula de Sherman-Morrison, eles decompõem o ganho em três componentes aditivos:
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   onde:

   • $a = u^\top \Sigma_i^{-1} u$ representa a contribuição de complexidade (termo log-determinante), medindo a interação da atualização com a métrica inversa regularizada.
   • $b = u^\top \Sigma_i^{-1} y$ representa a contribuição de ajuste de dados (data-fit), medindo o alinhamento entre a direção da atualização e o resíduo da predição atual.
   • $\|u\|^2_2$ representa a contribuição de traço (redução da variância do resíduo), que corresponde à redução exata do traço em um passo, em vez do proxy diagonal usado em métodos clássicos.

2. Atualizações Consistentes com Cholesky:
   Para garantir que a aproximação permaneça uma fatoração de Cholesky válida, o vetor de atualização $u$ é restrito à forma $u_p = t_p / \sqrt{(T_i)_{p,p}}$, onde $t_p$ é a $p$-ésima coluna da matriz de resíduo $T_i$. Essa restrição garante que o resíduo permaneça semidefinido positivo e que a entrada diagonal do pivô selecionado se torne zero.

3. Realização Algorítmica:
   Avaliar $\Delta L$ para todos os $n$ candidatos em cada etapa seria computacionalmente proibitivo ($O(n^2r^2)$). Para manter a eficiência, o método emprega uma estratégia de amostragem em lote (batched sampling):

   • Em cada iteração, um lote de $s$ pivôs candidatos é amostrado do conjunto de índices não utilizados.
   • A probabilidade de amostragem é proporcional às entradas diagonais do resíduo, idêntica à distribuição usada no RPCholesky.
   • A inversa regularizada $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ é aplicada a vetores de forma eficiente usando a identidade de Woodbury e atualizações incrementais de uma matriz auxiliar $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$.
   • Esta abordagem permite a avaliação do ganho para $s$ candidatos com um custo total de $O(snr^2)$, correspondendo à complexidade assintótica do RPCholesky até o fator de lote $s$.

Principais Contribuições

• Regra de Pivô Consciente do Objetivo: O artigo deriva o primeiro critério de seleção de pivô que maximiza explicitamente o ganho por passo da Energia Livre Variacional, em vez do erro da norma de traço.
• Garantias Teóricas: Os autores provam que qualquer sequência de atualizações de posto-1 consistentes com Cholesky produz uma sequência monotonicamente não decrescente de valores de VFE. A regra proposta seleciona o pivô que maximiza esse ganho garantido em cada etapa.
• Eficiência de Complexidade: O método alcança a mesma complexidade assintótica do Cholesky com pivoteamento aleatório ($O(snr^2)$) ao aproveitar as atualizações incrementais de Woodbury e a avaliação de candidatos em lote.
• Interpretação Hierárquica: O trabalho estabelece uma hierarquia de três níveis de regras de pivô:
  1. Nível 1: Greedy/RPCholesky clássico (usa o proxy diagonal para redução de traço).
  2. Nível 2: Maximizador exato de redução de traço (usa a coluna completa do resíduo, ignora dados/complexidade).
  3. Nível 3: $\Delta$-VFE (usa a coluna completa do resíduo, o vetor de dados e a inversa regularizada para otimizar a VFE completa).

Resultos
Experimentos numéricos nos conjuntos de dados Abalone e QM7 demonstram o seguinte:

• Otimização da VFE: O $\Delta$-VFE consistentemente alcança um limite mais justo na log-verossimilhança marginal (menor lacuna de VFE relativa) em comparação tanto ao método greedy quanto ao RPCholesky, particularmente em postos baixos a moderados ($r \le 1024$).
• Qualidade da Aproximação: O método mantém a qualidade de aproximação da norma de traço comparável ao RPCholesky. Ele não sacrifica a precisão de aproximação de kernel padrão para ganhar melhorias na VFE.
• Desempenho Preditivo: Em tarefas de regressão de GP, a melhoria da VFE traduz-se em redução dos erros de predição (RMSE e MAE) em postos baixos e moderados.
• Sensibilidade ao Tamanho do Lote: Aumentar o tamanho do lote $s$ produz retornos decrescentes em desempenho, mas melhora consistentemente a lacuna de VFE e a precisão preditiva. Mesmo pequenos tamanhos de lote (ex: $s=8$ ou $s=16$) proporcionam ganhos substanciais sobre o RPCholesky.

Significância
O artigo afirma que o método proposto preenche a lacavra entre a aproximação de matriz algébrica e os objetivos de inferência específicos da tarefa. Ao derivar um ganho exato de forma fechada para a VFE, os autores fornecem uma regra de pivô gulosa que está explicitamente alinhada com o objetivo de inferência probabilística dos processos gaussianos. Os resultados sugerem que para aplicações onde o funcional de matriz inclui termos de ajuste de dados ou de complexidade, otimizar apenas o erro da norma de traço é insuficiente, e que a seleção consciente do objetivo produz um desempenho prático superior sem incorrer em custos computacionais significativos. O método é apresentado como uma generalização direta do RPCholesky que incorpora informações adicionais sobre a função objetivo.