KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

Resumo Técnico: KSOS-BO: Melhoria da Amostragem em Otimização Bayesiana via Soma de Quadrados de Kernel

Enunciação do Problema
A Otimização Bayesiana (OB) é um framework padrão para a otimização global de funções de caixa-preta caras, amplamente utilizada no ajuste de hiperparâmetros, robótica e design científico. O procedimento de OB envolve duas etapas: ajustar um modelo substituto (tipicamente um Processo Gaussiano) e otimizar uma função de aquisição para selecionar o próximo ponto de consulta. Embora pesquisas significativas tenham se concentrado na melhoria de modelos substitutos e no design de funções de aquisição, a otimização da própria função de aquisição permanece um gargalo crítico. Na prática, este problema de otimização interno é frequentemente não convexo, multimodal e de alta dimensão. Otimizadores sem derivadas existentes (por exemplo, Evolução Diferencial, CMA-ES, Busca Sobol) frequentemente tratam isso como um problema genérico de caixa-preta, falhando em explorar explicitamente a natureza estruturada das paisagens de aquisição. Consequentemente, esses métodos podem ficar presos em ótimos locais ou exigir avaliações excessivas para encontrar candidatos de alta qualidade, limitando a eficiência geral do processo de OB.

Metodologia: KSOS-BO
Os autores propõem o KSOS-BO, um framework baseado em kernel e sem derivadas, projetado especificamente para otimizar funções de aquisição. O método adapta a abordagem de Soma de Quadrados de Kernel (KernelSOS) ao cenário de OB.

1. Formulação: A ideia central é reformular a minimização da função de aquisição $\alpha(x)$ como um problema de otimização global que busca o maior limite inferior $c$ tal que $\alpha(x) - c \geq 0$ para todo $x$ no domínio.
2. Relaxação de Kernel: Diferentemente dos métodos clássicos de Soma de Quadrados (SOS) restritos a objetivos polinomiais, o KSOS-BO utiliza Espaços de Hilbert de Reprodutores de Kernel (RKHS). Ele substitui bases polinomiais de dimensão finita por funções de kernel. A restrição de não negatividade é relaxada em um programa semidefinido (SDP) envolvendo uma matriz de kernel $K$ derivada de um conjunto finito de pontos amostrados.
3. Otimização e Recuperação: O algoritmo resolve um SDP para encontrar uma representação substituta baseada em kernel da função de aquisição deslocada. Em vez de otimizar diretamente no espaço de entrada, ele recupera um ponto candidato contínuo $x^*$ como uma combinação ponderada dos pontos amostrados. Isso permite que o método realize uma busca global estruturada usando apenas avaliações de função.
4. Integração: Em cada iteração de OB, o KSOS-BO amostra pontos para avaliar a função de aquisição atual, constrói o substituto KernelSOS, resolve o SDP para encontrar o próximo candidato e atualiza o modelo de OB.

Principais Contribuições

• Busca Global Estruturada: O artigo introduz uma aplicação inovadora do KernelSOS à otimização de aquisição, indo além da busca genérica de caixa-preta para explorar a natureza suave e estruturada das paisagens de aquisição induzidas por substitutos de Processo Gaussiano.
• Framework Sem Derivadas: O método opera sem exigir gradientes, tornando-o compatível com configurações padrão sem derivadas, enquanto fornece uma alternativa principial às buscas heurísticas baseadas em população.
• Ganhos de Desempenho: Os autores demonstram que, apesar de um custo computacional maior por iteração devido à etapa de SDP, o KSOS-BO alcança convergência mais rápida em tempo de relógio ao atingir soluções de alta qualidade com menos avaliações de aquisição.

Resultados Experimentais
Os autores avaliaram o KSOS-BO contra três baselines sem derivadas (Busca Sobol, Evolução Diferencial e CMA-ES) em 15 funções de referência com propriedades de paisagem variadas (multimodais, em forma de tigela, em forma de vale, em forma de platô e com quedas íngremes) em 10 dimensões.

• Melhoria no Arrependimento: O KSOS-BO alcançou o melhor desempenho em 10 de 15 benchmarks. Nessas funções de melhor desempenho, ele mostrou uma melhoria média no arrependimento de 81,16% em comparação com o segundo melhor otimizador.
• Eficiência em Tempo de Relógio: Embora o KSOS-BO incorra em maior sobrecarga computacional por iteração, ele convergiu mais rápido em tempo real. Nos 10 benchmarks onde ficou em primeiro lugar, alcançou uma melhoria média no tempo de relógio de 93,55%, efetivamente reduzindo pela metade o tempo necessário para atingir a mesma precisão que as baselines.
• Sensibilidade à Paisagem: O método se destacou em funções altamente multimodais (por exemplo, Ackley, Rastrigin, Griewank) e funções unimodais suaves (por exemplo, Rosenbrock, Dixon Price). No entanto, o desempenho degradou em funções com curvatura extrema, quedas íngremes ou regiões em forma de platô (por exemplo, Michalewicz, Zakharov, Styblinski Tang), onde a representação baseada em kernel foi considerada menos adequada.
• Robustez: Estudos de ablação indicaram que o KSOS-BO é robusto a variações no tamanho do design inicial, orçamentos de avaliação e escolhas de kernel (Gaussiano vs. Laplace), embora tenha superado consistentemente as baselines na maioria dos casos de teste.

Significado e Alegações
O artigo afirma que aprimorar apenas a etapa de otimização de aquisição produz melhorias mensuráveis no desempenho geral da Otimização Bayesiana. O significado principal reside em demonstrar que tratar a otimização de aquisição como um problema estruturado, solucionável via relaxações KernelSOS, é superior a tratá-lo como um problema genérico de caixa-preta.

Os autores observam modestamente que, embora o KSOS-BO seja eficaz para diversas estruturas de paisagem, não é uma solução universal; ele luta com características geométricas específicas como quedas íngremes ou platôs planos. Além disso, o método introduz uma compensação computacional: a etapa de SDP é mais cara do que estratégias evolutivas padrão, mas esse custo é justificado pela redução no número de avaliações de função caras necessárias para encontrar soluções ótimas. O trabalho sugere que direções futuras devem focar em melhorar a escalabilidade do KSOS-BO, explorar estratégias híbridas com refinamento local e testar em configurações de dimensão mais alta ou com restrições.