Resumo Técnico: Retirando o GP do Ciclo

Declaração do Problema

A Otimização Bayesiana (BO) é tradicionalmente empregada para problemas de caixa-preta onde as avaliações de função são caras, resultando em poucas observações ($N$). No entanto, uma classe crescente de problemas, denominada Otimização Bayesiana com Muitas Observações (BOMO), envolve avaliações rápidas e paralelizáveis (por exemplo, simulações em grande escala) onde $N$ pode atingir dezenas de milhares.

No regime BOMO, os métodos padrão de BO enfrentam um gargalo de escalabilidade. As abordagens tradicionais dependem de substitutos de Processo Gaussiano (GP). Embora implementações modernas tenham reduzido a complexidade de tempo de aquisição de $O(N^3)$ para aproximadamente $O(N^2)$, a necessidade de ajustar os hiperparâmetros do GP a cada iteração permanece um ônus computacional significativo. Esse processo de ajuste, frequentemente envolvendo a reconstrução da matriz de kernel, escala mal com $N$, impedindo a aplicação de BO a problemas com contagens massivas de observações.

Metodologia

Os autores propõem TuRBO-ENN, um método que substitui o substituto GP no framework de Otimização Bayesiana com Região de Confiança (TuRBO) por uma alternativa leve chamada Vizinhos Mais Próximos Epistêmicos (ENN).

1. Vizinhos Mais Próximos Epistêmicos (ENN)

O ENN é um substituto baseado em K-vizinhos mais próximos (KNN) projetado para estimar tanto valores de função quanto incerteza (epistêmica e aleatória) com escalabilidade linear.

• Construção do Substituto: Para um ponto de consulta $x$, o ENN identifica os $K$ vizinhos mais próximos no conjunto de observações $D$. Ele trata cada vizinho como uma estimativa independente do valor da função.
• Quantificação da Incerteza:
  • Variância Aleatória ($\sigma_a^2$): Modelada como a soma de um nível de ruído base ($s_0^2$) e a escala de ruído específica da observação ($s_m^2$).
  • Variância Epistêmica ($\sigma_e^2$): Modelada como proporcional ao quadrado da distância euclidiana entre o ponto de consulta e o vizinho ($c_e d^2(x, x_m)$).
• Agregação: A estimativa final da média $\mu(x)$ e as estimativas de variância são computadas usando uma média ponderada pela precisão (ponderação inversa à variância) dos $K$ vizinhos. Isso evita os cálculos de covariância em pares $O(N^2)$ exigidos pelos GPs.
• Complexidade: Encontrar os $K$ vizinhos mais próximos usando um heap máximo ou biblioteca Faiss leva $O(N \ln K)$ por consulta. O ajuste dos hiperparâmetros ($s_0, c_e$) é realizado via Estimativa de Máxima Verossimilhança do Tipo-II (MLE) em uma pseudoverossimilhança de Validação Cruzada Leave-One-Out (LOOCV), aproximada usando um subconjunto de tamanho fixo para manter a escalabilidade $O(N)$.

2. Integração TuRBO-ENN

O método integra o ENN ao algoritmo TuRBO, que utiliza uma região de confiança para focar os esforços de busca.

• Objetivos Ruidosos: Para problemas com ruído, o método ajusta os hiperparâmetros do ENN e usa a função de aquisição Upper Confidence Bound (UCB): $UCB(x) = \mu(x) + \sigma(x)$.
• Objetivos Sem Ruído: Para problemas determinísticos, os autores propõem uma variante sem ajuste. Como o ajuste de hiperparâmetros é desnecessário quando se sabe que o ruído é zero, o método seleciona candidatos via Classificação Não Dominada (NDS) sobre o par $(\mu(x), \sigma(x))$. Isso elimina completamente a etapa de ajuste, reduzindo ainda mais o tempo de proposta.
• Otimização Pseudo-Bayesiana (PBO): Os autores verificam que o TuRBO-ENN satisfaz as condições para Otimização Pseudo-Bayesiana (Chen & Lam, 2025), garantindo garantias teóricas de convergência.

Contribuições Principais

1. Substituto ENN: Introdução de um substituto KNN leve que estima valores de função e incerteza com tempo de ajuste e consulta $O(N)$, contrastando com a escalabilidade $O(N^2)$ ou $O(N^3)$ dos GPs.
2. Algoritmo TuRBO-ENN: Desenvolvimento de um método de BO que substitui o GP e a Amostragem de Thompson do TuRBO por ENN e UCB (ou NDS para casos sem ruído).
3. Validação Empírica: Demonstração de que o TuRBO-ENN reduz o tempo de proposta (ajuste + aquisição) em uma a duas ordens de grandeza em comparação com o TuRBO-GP em problemas com até 50.000 observações, sem sacrificar a qualidade da solução.
4. Garantia Teórica: Verificação de que o TuRBO-ENN se qualifica como um método PBO, herdando garantias de convergência.
5. Código Aberto: Lançamento do pacote Python ennbo.

Resultados Experimentais

Os autores compararam o TuRBO-ENN com métodos de última geração (TuRBO-GP, Optuna, SMAC, CMA-ES, DNGO, Vecchia GP) em cinco tarefas de simulação (LunarLander, Hopper, BipedalWalker, Push) e uma tarefa de otimização de hiperparâmetros (LASSO-DNA) com dimensões variando de 12 a 180.

• Escalabilidade: Enquanto métodos baseados em GP (por exemplo, turbo-one, ucb) exibiram escalabilidade aproximada de $O(N^2)$ no tempo de proposta, o TuRBO-ESC escalou linearmente ($O(N)$).
• Aceleração: O TuRBO-ENN alcançou acelerações variando de 8,5x a 151x sobre o TuRBO-GP, com ganhos maiores observados em contagens de observação mais altas ($N$) e em configurações de ruído congelado (sem ruído) onde o ajuste de hiperparâmetros foi omitido.
• Qualidade da Solução: O TuRBO-ENN igualou o desempenho de otimização (qualidade da solução) do TuRBO-GP em todas as tarefas testadas.
• Tarefas de Ajuste: Em tarefas puras de regressão (dados sintéticos), o ENN foi ordens de grandeza mais rápido para ajustar do que GPs Exatos, SVGP e substitutos de redes neurais, mantendo log-verossimilhanças competitivas no conjunto de teste.

Significado e Alegações

O artigo argumenta que, à medida que as capacidades de simulação crescem, o gargalo na Otimização Bayesiana desloca-se do custo de avaliação da função para o custo computacional do próprio algoritmo de otimização (tempo de proposta). Ao remover o Processo Gaussiano do ciclo, o TuRBO-ENN permite que a BO escale para regimes com dezenas de milhares de observações, onde os métodos tradicionais se tornam computacionalmente proibitivos.

Os autores afirmam modestamente que seu método fornece uma alternativa prática e escalável para problemas BOMO, oferecendo uma opção "sem ajuste" para simulações determinísticas e uma opção de escalabilidade linear para as ruidosas, tudo enquanto mantém as propriedades de convergência teórica da otimização bayesiana. Eles notam que, embora alcancem garantias de convergência via axiomas PBO, não fornecem limites específicos de arrependimento. Direções de trabalho futuro sugeridas incluem adaptar o ENN para algoritmos de vizinhos mais próximos aproximados para escalabilidade $O(\ln N)$ e explorar ponderação específica de dimensão na métrica de distância.