Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference

Resumo Técnico: Warm-Starting de Processos Gaussianos Iterativos para Inferência Sequencial Mais Rápida

Declaração do Problema
Os Processos Gaussianos (GPs) são modelos não paramétricos poderosos para regressão, classificação e otimização bayesiana, contudo sua escalabilidade é limitada pelo custo $O(n^3)$ de inverter a matriz de covariância para computar a posterior. Embora solucionadores iterativos (ex: Gradiente Conjugado, Gradiente Descendente Estocástico, Projeções Alternadas) ofereçam uma maneira de evitar custos cúbicos ao aproximar a solução, eles tipicamente requerem muitas iterações para convergir. Em configurações sequenciais — como aprendizado ativo, predição online e otimização bayesiana — onde os dados chegam incrementalmente e a posterior deve ser atualizada frequentemente, a abordagem padrão de "cold-start" (inicializando todos os pesos com zero e descartando a computação anterior) torna-se um gargalo. Essa ineficiência limita a eficácia dos GPs iterativos em ambientes dinâmicos.

Metodologia
O artigo propõe três estratégias de "warm-start" para inicializar solucionadores lineares iterativos ao atualizar uma posterior de GP com novos pontos de dados. Em vez de resolver o sistema linear estendido do zero, esses métodos aproveitam a solução ($u_1$) do sistema linear anterior, menor, para inicializar os pesos ($v$) do novo sistema, maior.

O problema é formulado como a resolução de um sistema linear estendido $Hv = b$, onde a matriz $H$ e o vetor $b$ são particionados para incluir os dados existentes (bloco 1) e os novos dados (bloco 2). Os três métodos de inicialização propostos são:

1. Naïve Warm-Start: Os pesos correspondentes aos dados originais ($v_1$) são inicializados com a solução anterior ($u_1$), enquanto os pesos para os novos dados ($v_2$) são inicializados com zero.
   $$v \leftarrow \begin{bmatrix} u_1 \\ 0 \end{bmatrix}$$
2. Residual Line Search: Este método melhora a abordagem naïve ao realizar uma busca de linha para determinar o escalar ótimo $\alpha$ para os novos pesos ($v_2$) na direção do resíduo. Isso minimiza o objetivo quadrático dado o $v_1 = u_1$ fixo.
   $$v_2 = \alpha^* r, \quad \text{onde } r = b_2 - H_{12}^\top u_1 \text{ e } \alpha^* = \frac{r^\top r}{r^\top H_{22} r}$$
3. Marginal System Solve: O método mais complexo, que resolve um sistema linear marginal menor ($H_{22}v_2 = r$) para encontrar o $v_2$ que minimiza o objetivo dado $v_1 = u_1$.
   $$v_2 = H_{22}^{-1} r$$

Análise Teórica
Os autores fornecem suporte teórico usando a distância do Espaço de Hilbert de Núcleo Reproduzível (RKHS), definida como $d^2 = (v - v^*)^\top H (v - v^*)$, onde $v^*$ é a solução exata. Eles demonstram que:

• O naïve warm-start reduz estritamente a distância RKHS em comparação com um cold-start ($d^2_{cold} - d^2_{naïve} \geq 0$).
• Tanto o residual line search quanto o marginal system solve reduzem ainda mais essa distância ($d^2_{naïve} > d^2_{line-search} > d^2_{marginal-solve}$).
• Reduzir a distância RKHS é equivalente a reduzir o resíduo inicial do sistema linear, o que correlaciona diretamente com menos iterações necessárias para a convergência.

Contribuições Principais e Resultados
O artigo introduz essas três estratégias de inicialização e valida sua eficácia através de análise teórica e experimentos empíricos em benchmarks de regressão e tarefas de otimização bayesiana.

• Experimentos de Regressão: Usando conjuntos de dados do repositório UCI (ex: 3droad, protein, buzz), os autores compararam o número de iterações necessárias para a convergência contra uma linha de base de cold-start.

  • Acelerações: Ao resolver para uma tolerância específica, o warm-starting alcançou acelerações de até 1.4× para Gradiente Conjugado (CG), 1.5× para Gradiente Descendente Estocástico (SGD) e 4.0× para Projeções Alternadas (AP).
  • Casos Extremos: Para AP, as acelerações chegaram a até 19× em certos conjuntos de dados, particularmente quando a razão de novos dados para dados existentes é pequena.
  • Precisão: Sob orçamentos de computação fixos (iterações limitadas), o warm-starting produziu estimativas de posterior mais precisas, reduzindo a norma do resíduo final.

• Otimização Bayesiana (Parallel Thompson Sampling): Em um experimento de amostragem de Thompson paralela com um orçamento de computação fixo, os métodos foram avaliados em sua capacidade de maximizar uma função objetivo.

  • Ganhos de Desempenho: Os métodos de warm-start melhoraram o valor máximo final encontrado na função objetivo em até 13% para CG, 46% para SGD e 10% para AP em comparação com o cold-starting.
  • Progresso Acumulado: Os resultados indicaram que o progresso do solucionador se acumula ao longo de múltiplas resoluções sequenciais quando se usa warm-starting, em vez de resetar, levando a amostras de posterior mais precisas e melhor desempenho de otimização.

Significância
O artigo estabelece o warm-starting como uma ferramenta simples, eficaz e amplamente aplicável para escalar processos gaussianos em configurações sequenciais. Ao explorar soluções de sistemas lineares menores, esses métodos aceleram substancialmente a convergência sem exigir aproximações esparsas que sacrificam a precisão. Os autores afirmam que esta abordagem aborda diretamente o gargalo de escalabilidade em tarefas de tomada de decisão sequencial, permitindo atualizações de posterior mais frequentes e precisas dentro das mesmas restrições computacionais. Os métodos são apresentados como melhorias práticas que podem ser integradas com solucionadores iterativos existentes (CG, SGD, AP) para melhorar a eficiência de aplicações baseadas em GP.