Bayesian Optimistic Optimisation with Exponentially Decaying Regret

1. Formulação do Problema

O artigo aborda o problema de otimização global para funções caras, sem ruído e de caixa-preta $f(x)$, onde $x \in \mathcal{X} \subset \mathbb{R}^D$. O objetivo é encontrar o máximo global $x^*$ com um orçamento limitado de avaliações de função $N$.

O desempenho é medido pelo arrependimento simples:
$$r_N = \sup_{x \in \mathcal{X}} f(x) - \max_{1 \le i \le N} f(x_i)$$

Limitações Existentes:

• Otimização Bayesiana (BO): Algoritmos padrão de BO (e.g., GP-UCB, GP-EI) tipicamente alcançam limites de arrependimento sub-lineares (e.g., $O(\sqrt{\frac{\log N}{N}})$ ou $O(1/\sqrt{N})$). Um grande gargalo é que a BO requer a resolução de um problema de otimização auxiliar não convexo (maximização da função de aquisição) a cada iteração, o que é computacionalmente caro e difícil em altas dimensões.
• Otimização Otimista (Baseada em Árvores): Algoritmos como SOO e BaMSOO particionam o espaço de busca hierarquicamente. Embora evitem a otimização auxiliar, eles sofrem de uma correlação negativa estrita entre o fator de ramificação $m$ (granularidade do particionamento) e o número de expansões da árvore. Para alcançar particionamentos finos (grande $m$), eles devem avaliar muitos nós filhos, consumindo o orçamento de avaliações $N$ rapidamente. Consequentemente, seus limites de arrependimento no pior caso são frequentemente limitados a $O(e^{-\sqrt{N}})$ ou taxas sub-lineares.

Os autores perguntam: Podemos projetar um algoritmo prático que combine a eficiência de modelo da BO com os benefícios estruturais da otimização otimista baseada em árvores para alcançar um limite de arrependimento mais apertado (especificamente $O(N^{-\sqrt{N}})$) sem o custo computacional da otimização auxiliar?

2. Metodologia: O Algoritmo BOO

Os autores propõem a Otimização Otimista Bayesiana (BOO), um algoritmo inovador que integra Processos Gaussianos (GP) com uma busca em árvore hierárquica modificada.

Inovações Chave

1. Desacoplamento do Fator de Ramificação das Avaliações:

   • Abordagem Tradicional: Em SOO/BaMSOO, expandir um nó requer avaliar $m$ filhos. Assim, o número de expansões é limitado a $N/m$.
   • Abordagem BOO: O algoritmo seleciona um nó para expansão baseado no Limite Superior de Confiança do GP (GP-UCB). Crucialmente, ele avalia apenas a função objetivo no nó pai selecionado, não em seus $m$ filhos. Os filhos são adicionados à árvore estruturalmente, mas permanecem não avaliados até serem selecionados posteriormente.
   • Resultado: Isso "desata" o fator de ramificação $m$ do orçamento de avaliações. O algoritmo pode usar um $m$ muito grande para criar particionamentos extremamente finos sem pagar o custo de $m$ avaliações por etapa.

2. Procedimento de Particionamento Novel $P(m; a, b)$:

   • Em vez de dividir apenas o lado mais longo de uma célula (padrão no SOO), a BOO decompõe o fator de ramificação $m = a^b$.
   • Ela divide a célula ao longo de suas $b$ dimensões mais longas em $a$ partes iguais cada.
   • Ao definir $b = D$ (a dimensionalidade), o algoritmo particiona todas as dimensões simultaneamente. Isso permite que o espaço de busca seja refinado muito mais rápido em todas as direções comparado à divisão sequencial de dimensões.

3. Estratégia de Amostragem:

   • O algoritmo mantém um modelo GP.
   • A cada passo, ele seleciona o nó folha com o maior valor de GP-UCB.
   • Ele avalia $f$ apenas no centro deste nó selecionado.
   • Ele atualiza o GP e a estrutura da árvore, adicionando $m$ filhos ao nó selecionado.

Fluxo do Algoritmo (Simplificado)

1. Inicializar uma árvore com um nó raiz.
2. Selecionar o nó folha $(h, i)$ com o valor máximo de GP-UCB $U_p(c_{h,i})$.
3. Se $U_p(c_{h,i}) \ge v_{max}$ (melhor valor observado atual):
   • Avaliar $f$ no centro do nó.
   • Atualizar o conjunto de dados e reajustar o GP.
   • Expandir o nó adicionando $m$ filhos usando a regra de particionamento $P(m; a, b)$.
4. Repetir até que o orçamento $N$ seja esgotado.

3. Contribuições Teóricas e Análise de Arrependimento

O artigo fornece uma análise teórica rigorosa sob a suposição de que $f$ é amostrada de um Processo Gaussiano com um kernel Matérn com parâmetro de suavidade $\nu > 4 + \frac{D}{2}$.

• Limite de Arrependimento: Os autores provam que a BOO alcança um limite de arrependimento simples de:
  $$r_N = O(N^{-\sqrt{N}})$$
  Este é um arrependimento decrescente exponencial que é estritamente mais apertado que o limite $O(e^{-\sqrt{N}})$ de algoritmos otimistas anteriores de última geração (como IMGPO) e significativamente melhor que os limites padrão de BO.

• Mecanismo Teórico Chave:

  • A prova baseia-se em limitar o tamanho do "conjunto de expansão" (nós que poderiam potencialmente conter o ótimo).
  • Ao usar o particionamento novel ($b=D$) e o grande fator de ramificação $m$, a "dimensão de quase-optimalidade" é mostrada como efetivamente 0.
  • O desacoplamento de $m$ das avaliações permite que o algoritmo explore o espaço com alta granularidade ($m$ grande) enquanto mantém um baixo custo de avaliação, levando à taxa de convergência aprimorada.

4. Resultados Experimentais

Os autores validaram a BOO em benchmarks sintéticos e tarefas reais de ajuste de hiperparâmetros de aprendizado de máquina.

• Baselines: Comparado contra GP-EI, GP-UCB, SOO, BaMSOO e IMGPO.
• Funções Sintéticas: Testado nas funções Hartmann3, Schwefel e Shekel.
  • Resultado: A BOO superou consistentemente todas as baselines em termos de velocidade de convergência (distância logarítmica ao ótimo). Ela alcançou o melhor desempenho em Hartmann e Schwefel, e desempenho competitivo em Shekel.
• Ajuste de Hiperparâmetros:
  • Tarefas: Ajuste de ElasticNet, MLP e XGBoost nos conjuntos de dados MNIST e Skin Segmentation.
  • Resultado: A BOO alcançou erros de previsão menores comparado a todas as baselines. Para o XGBoost, ela superou as outras por uma ampla margem.
• Eficiência Computacional:
  • A BOO é significativamente mais rápida que GP-EI e GP-UCB porque evita a maximização cara de funções de aquisição sobre espaços contínuos.
  • É ligeiramente mais lenta que o IMGPO devido à sobrecarga de gerenciar uma árvore maior (grande $m$), mas o trade-off produz desempenho de otimização superior.

5. Significado e Conclusão

• Quebrando a Barreira do Arrependimento: Este é o primeiro algoritmo prático a alcançar um limite de arrependimento de $O(N^{-\sqrt{N}})$ para otimização bayesiana, superando os limites teóricos de métodos otimistas e bayesianos anteriores.
• Praticidade: Diferente de abordagens teóricas anteriores que exigiam amostragem impraticável (como amostragem de $\delta$-cobertura), a BOO é implementável e eficiente.
• Sinergia: O trabalho conecta com sucesso a lacuna entre Otimização Baseada em Modelo (BO) e Otimização Otimista Livre de Modelo, demonstrando que incorporar um modelo GP em uma estrutura baseada em árvores com uma estratégia de amostragem específica pode produzir melhorias exponenciais na convergência.
• Trabalho Futuro: Os autores notam planos para estender o método para configurações ruidosas e espaços de dimensões mais altas.

Em resumo, o artigo apresenta um avanço significativo na teoria e prática da otimização global ao introduzir um mecanismo para desacoplar a granularidade da busca do custo de avaliação, resultando em um limite de arrependimento de última geração e desempenho empírico superior.