Resumo Técnico: BAXUS – Otimização Bayesiana Adaptativa em Subespaços Aninhados

Declaração do Problema

A Otimização Bayesiana de Alta Dimensão (HDBO) visa otimizar funções de caixa preta caras de avaliar com dezenas a centenas de dimensões de entrada. Embora avanços recentes tenham estendido o escopo da Otimização Bayesiana (BO) para áreas como ciências da vida, busca de arquitetura neural e robótica, os métodos mais avançados enfrentam limitações significativas à medida que a dimensionalidade aumenta.

As abordagens existentes geralmente se enquadram em duas categorias, ambas com desvantagens críticas:

1. Métodos de Região de Confiança (ex: TURBO): Estes otimizam sobre regiões limitadas locais (regiões de confiança) dentro do espaço de entrada completo. Embora eficazes para dimensões moderadas, seu desempenho degrada em dimensões muito altas porque as regiões de confiança retêm a dimensionalidade completa do problema, sofrendo com a maldição da dimensionalidade.
2. Métodos de Embedding Linear (ex: REMBO, HESBO, ALEBO): Estes assumem a existência de um "subespaço ativo" de baixa dimensão e projetam o espaço de entrada de alta dimensão em um espaço alvo de dimensão inferior. No entanto, esses métodos exigem que o usuário "adivinhe" a dimensionalidade efetiva ($d_e$) do subespaço ativo. Se a dimensionalidade alvo escolhida ($d$) for muito pequena, o subespaço não pode representar o ótimo global; se $d$ for muito grande, a otimização desacelera devido à maldição da dimensionalidade. Além disso, métodos como HESBO dependem de hashing aleatório que oferece garantias de pior caso inferiores para conter um ótimo em comparação com outros embeddings.

O desafio central é desenvolver um método HDBO que encontre confiavelmente ótimos globais sem exigir conhecimento prévio da dimensionalidade do subespaço ativo, ao mesmo tempo em que evita a degradação de desempenho associada a espaços de busca de alta dimensão.

Metodologia: BAXUS

Os autores propõem o BAXUS (Otimização Bayesiana com subespaços em expansão adaptativa), uma abordagem fundamentada teoricamente que ajusta dinamicamente a dimensionalidade do espaço de otimização.

1. Subespaços Aninhados Adaptativos

Em vez de fixar a dimensionalidade alvo, o BAXUS opera sobre uma família de subespaços aleatórios aninhados. O algoritmo começa com um espaço alvo de baixa dimensão ($d_{init}$) e aumenta progressivamente a dimensionalidade à medida que coleta mais dados.

• Inicialização: O BAXUS começa com uma dimensão alvo pequena $d_0$.
• Expansão: À medida que a otimização prossegue, a dimensionalidade alvo é aumentada "dividindo" as dimensões alvo existentes. Este processo continua até que a dimensionalidade alvo alcance aproximadamente a dimensionalidade de entrada $D$ ou o orçamento de avaliação seja esgotado.
• Retenção de Observações: Uma característica crítica do BAXUS é sua capacidade de reter observações de espaços de dimensão inferior ao expandir para dimensões mais altas. Quando uma dimensão alvo é dividida, as dimensões de entrada contribuintes são reatribuídas à dimensão original e a novos intervalos. Os valores da função (observações) são copiados para as novas dimensões, garantindo que os dados coletados na fase de baixa dimensão permaneçam válidos na fase de maior dimensão.

2. O Embedding Esparsos BAXUS

O BAXUS utiliza um embedding linear esparso novel para mapear o espaço alvo $Y \in \mathbb{R}^d$ para o espaço de entrada $X \in \mathbb{R}^D$.

• Estrutura: A matriz de embedding $S^\top \in \{0, \pm 1\}^{d \times D}$ é esparsa, o que significa que cada coluna (dimensão de entrada) tem exatamente uma entrada não nula.
• Balanceamento de Intervalos: Diferentemente do HESBO, que atribui dimensões de entrada a dimensões alvo uniformemente ao acaso (levando a tamanhos de intervalo variáveis), o BAXUS impõe que o número de dimensões de entrada contribuintes por dimensão alvo (tamanho do intervalo) difira por no máximo um. Essa atribuição "balanceada" é alcançada permutando as dimensões de entrada e dividindo-as em $d$ intervalos.
• Vantagem Teórica: Os autores provam que este embedding esparso balanceado fornece uma probabilidade de sucesso de pior caso estritamente maior (a probabilidade de o espaço alvo conter um ótimo global) do que o embedding HESBO para dimensões de entrada finitas. À medida que $D \to \infty$, a probabilidade de sucesso do BAXUS converge para a do HESBO.

3. Estratégia de Região de Confiança e Divisão

O BAXUS integra a expansão do embedding com uma abordagem de Região de Confiança (TR) semelhante ao TURBO:

• Regiões de Confiança: A otimização ocorre dentro de regiões de confiança hiper-retangulares no espaço alvo, escaladas pelos comprimentos de escala do GP.
• Gatilho de Expansão: A dimensionalidade alvo é aumentada quando o comprimento do lado base da região de confiança cai abaixo de um limite mínimo (indicando que a região atual é muito pequena ou que o algoritmo está preso).
• Controle de Falhas: O número de "falhas" permitidas (iterações consecutivas sem melhoria) antes que uma divisão ocorra é reduzido com base na dimensionalidade alvo atual. Isso garante que o algoritmo possa atingir dimensões altas dentro de um orçamento de avaliação fixo.
• Convergência: O algoritmo é provado para alcançar convergência global. Uma vez que a dimensionalidade alvo atinge a dimensionalidade de entrada $D$, o BAXUS comporta-se como o TURBO, que é conhecido por convergir globalmente.

Contribuições Principais

1. Desenvolvimento de Algoritmo: Os autores introduzem o BAXUS, que alcança confiavelmente soluções excelentes em um amplo conjunto de tarefas de alta dimensão, superando os métodos mais avançados atuais.
2. Teoria de Embedding Novel: Eles apresentam uma nova família de embeddings aleatórios aninhados com três propriedades-chave:
   • Fornece uma garantia de pior caso maior para conter um ótimo global em comparação com o embedding HESBO.
   • É um embedding esparso ótimo, o que significa que nenhum outro embedding esparso tem uma probabilidade de sucesso de pior caso maior para as mesmas dimensões de entrada, alvo e efetiva.
   • Sua probabilidade de conter um ótimo converge para a probabilidade do HESBO à medida que a dimensionalidade de entrada $D \to \infty$.
3. Avaliação Abrangente: O artigo fornece evidências empíricas extensas demonstrando a superioridade do BAXUS sobre TURBO, SAASBO, ALEBO, HESBO, CMA-ES e busca aleatória em diversos benchmarks.

Resultados Experimentais

Os autores avaliaram o BAXUS em uma coleção de tarefas de otimização de hiperparâmetros de 388 dimensões, problemas de design de 124 dimensões e benchmarks com subespaços ativos conhecidos (LASSO, MOPTA08, BRANIN, HARTMANN).

• Desempenho: O BAXUS superou consistentemente os métodos mais avançados. No benchmark SVM de 388D, o BAXUS adaptou-se à dimensionalidade alvo apropriada e encontrou soluções melhores mais rápido do que o TURBO e o CMA-ES. No benchmark LASSO-HARD de 1000D, o BAXUS alcançou soluções consideravelmente melhores do que todos os concorrentes, incluindo métodos que dependem de suposições de subespaço ativo (SAASBO, ALEBO, HESBO), que falharam em se beneficiar da estrutura do subespaço ativo.
• Robustez: O BAXUS demonstrou robustez ao ruído observacional, mantendo um desempenho forte em variantes ruidosas de benchmarks onde concorrentes como SAASBO e CMA-ES degradaram significativamente.
• Estudos de Ablação: Substituir o embedding BAXUS por um embedding HESBO aninhado resultou em desempenho significativamente pior, confirmando que a estratégia de balanceamento de intervalos é um motor chave do sucesso.
• Comparação com Embeddings Fixos: O BAXUS superou a execução do TURBO com uma dimensionalidade alvo fixa, mostrando que a estratégia de expansão adaptativa é superior a escolhas estáticas de $d$.

Significado e Alegações

O artigo alega que o BAXUS aborda as limitações críticas dos métodos HDBO atuais ao remover a necessidade de os praticantes "adivinharem" a dimensionalidade efetiva do problema. Ao expandir adaptativamente o espaço de busca, o BAXUS aproveita a eficiência da otimização de baixa dimensão enquanto garante que o espaço de busca eventualmente cubra o espaço de entrada completo, assegurando assim que o ótimo global seja alcançável.

Os autores afirmam que o BAXUS é um otimizador "pronto para uso" (out-of-the-box) que alcança desempenho robusto em uma ampla variedade de tarefas de alta dimensão sem exigir suposições específicas sobre a estrutura do problema (como subespaços ativos alinhados aos eixos). O trabalho visa tornar a Otimização Bayesiana de Alta Dimensão mais acessível e confiável para aplicações em ciência e indústria, onde o número de parâmetros ajustáveis é grande e sua dimensionalidade efetiva é desconhecida.