Resumo Técnico: Otimização Bayesiana em Lote Escalável via Funções de Aquisição de Subespaço

Declaração do Problema

A Otimização Bayesiana (BO) é um framework poderoso para resolver problemas de otimização de caixa-preta caros. Embora a BO padrão opere sequencialmente, selecionando um ponto de amostra por vez, essa abordagem é ineficiente quando recursos de computação paralela estão disponíveis. Para aproveitar o paralelismo, algoritmos de Otimização Bayesiana em Lote (Batch Bayesian Optimization) são necessários para avaliar múltiplas amostras simultaneamente.

No entanto, as abordagens de lote existentes enfrentam problemas significciais de escalabilidade à medida que o tamanho do lote ($q$) aumenta:

• Melhoria Esperada Multi-ponto (qEI): Embora teoricamente sólida, a otimização da qEI envolve um espaço de busca de dimensão $d \times q$ (onde $d$ é a dimensão do problema). À medida que $q$ cresce, o custo computacional de avaliar a função de distribuição cumulativa multivariada e a dificuldade de otimizar a função de aquisição aumentam exponencialmente, tornando a qEI e suas variantes (ex: FqEI, qLogEI) impraticáveis para grandes tamanhos de lote (tipicamente $q > 10$).
• Abordagens Heurísticas (ex: Kriging Believer, Constant Liar, Local Penalization): Estes métodos frequentemente dependem de pontos "falsos" ou funções de penalidade artificiais para simular efeitos de lote. À medida que o tamanho do lote aumenta, a acumulação desses pontos artificiais degrada a precisidade do modelo de Processo Gaussiano (GP), potencialmente induzindo o erro na direção de busca e reduzindo a eficiência da otimização.
• Abordagens Multi-objetivo e Multi-modelo: Métos que treinam múltiplos modelos substitutos ou resolvem problemas de otimização multi-objetivo frequentemente incorrem em altos custos computacionais que não escalam bem com grandes tamanhos de lote.

O desafio central abordado neste trabalho é projetar uma estratégia de aquisição em lote que permaneça computacionalmente tratável e eficaz para avaliações em lote de larga escala sem sofrer com a maldição da dimensionalidade ou degradação do modelo.

Metodologia

Os autores propõem uma abordagem inovadora chamada Funções de Aquisição de Subespaço, que estende as funções de aquisição existentes (especificamente a Melhoria Esperada, mas também adaptável a PI e UCB) para operar dentro de subespaços selecionados aleatoriamente e alinhados aos eixos.

Conceito Central: Melhoria Esperada de Subespaço (SSEI)

Em vez de buscar $q$ pontos no espaço de design completo de $d$ dimensões simultaneamente, o método:

1. Seleciona Subespaços: Seleciona aleatoriamente um conjunto de subespaços alinhados aos eixos. Um subespaço de $k$ dimensões alinhado aos eixos é definido pela escolha de $k$ coordenadas das $d$ dimensões originais, fixando as $d-k$ coordenadas restantes nos valores da solução atual de melhor desempenho ($x_{min}$).
2. Otimiza Localmente: Para cada subespaço selecionado, a função de aquisição padrão (ex: EI) é otimizada apenas sobre as $k$ variáveis ativas. As variáveis não selecionadas permanecem fixas em $x_{min}$.
3. Gera o Lote: Um ponto de consulta é selecionado de cada subespaço único. Se o tamanho de lote requerido $q$ exceder o número de subespaços disponíveis ($N = 2^d - 1$), o método utiliza a Melhoria Esperada de Multi-ponto de Subespaço (SSqEI), que otimiza múltiplos pontos dentro de um único subespaço.

Estrutura Computacional

O algoritmo proposto (Algoritmo 1) opera da seguinte forma:

• Inicialização: Gera amostras iniciais e treina um modelo GP.
• Seleção de Subespaço: Desenha aleatoriamente um inteiro $k \in [1, d]$ e, em seguida, uma combinação aleatória de $k$ coordenadas para formar um subespaço. Isso evita o custo computacional de enumerar todos os subespaços possíveis.
• Otimização da Aquisição:
  • Se $q \le N$: Seleciona $q$ subespaços distintos e otimiza a SSEI padrão em cada um para encontrar um ponto por subespaço.
  • Se $q > N$: Distribui os $q$ pontos entre os $N$ subespaços disponíveis (otimizando múltiplos pontos por subespaço usando SSqEI).
• Avaliação: Avalia o lote resultante de $q$ pontos em paralelo.
• Atualização: Atualiza o modelo GP com as novas observações e repete o processo.

A dimensionalidade do problema de otimização para a função de aquisição é reduzida de $d \times q$ para aproximadamente $k \times 1$ (ou $k \times q_i$ para SSqEI), onde a dimensão esperada $E[k] \approx d/2$. Isso reduz significativamente a complexidade da otimização da aquisição.

Principais Contribuições

1. Estratégia de Lote Escalável: O artigo introduz um método para estender a otimização bayesiana para grandes tamanhos de lote ao desacoplar a seleção do lote em otimizações de subespaço independentes ou de baixa dimensão, evitando a complexidade exponencial da qEI.
2. Simplicidade e Generalidade: A abordagem não requer hiperparâmetros adicionais e é aplicável a uma ampla gama de funções de aquisição (demonstrado em EI, PI e UCB). É conceitualmente simples: "desenhar subespaços, otimizar localmente, agregar".
3. Robustez à Dimensionalidade: Ao restringir a busca a subespaços alinhados aos eixos ancorados na solução atual de melhor desempenho, o método equilibra naturalmente a exploração (via seleção aleatória de subespaços) e a explotação (via busca local ao redor de $x_{min}$), tornando-o particularmente eficaz em espaços de alta dimensão.

Resultados Experimentais

Os autores avaliaram o método proposto (SSEI) contra dez algoritmos de lote estado da arte (incluindo qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB e Busca Aleatória) em 60 problemas de benchmark sintéticos (GPMean, SumSquares, Rosenbrock, etc.) em dimensões $d \in \{2, 4, 8, 10, 20, 30\}$ e tamanhos de lote $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$.

• Desempenho vs. BO Sequencial: Quando $q=1$, o SSEI performa de forma semelhante ao EI padrão em problemas de baixa dimensão, mas supera significativamente este em problemas de alta dimensão ($d \ge 8$). Os autores atribuem isso ao fato de que o EI sequencial tem dificuldade em otimizar a função de aquisição em altas dimensões, enquanto a busca de subespaço local do SSEI encontra melhores ótimos locais para a função de aquisição.
• Escalabilidade com Tamanho de Lote:
  • Lotes Pequenos a Médios ($q \le 32$): O SSEI alcança um aumento de velocidade quase linear em termos de tempo de execução (iterações) enquanto mantém o desempenho comparável ou superior a outros métodos de lote quando medido por avaliações de função.
  • Grandes Lotes ($q = 128$): O SSEI supera significativamente todos os algoritmos de lote comparados, incluindo variantes da qEI que falham ou degradam significativamente nesta escala. O método proposto converge mais rápido e encontra melhores soluções finais.
• Comparação com Algoritmos Específicos:
  • vs. qEI/qLogEI/FqEI: O SSEI é superior, especialmente conforme $d$ e $q$ aumentam, porque evita a maldição da dimensionalidade $d \times q$.
  • vs. TuRBO: O SSEI performa de forma competitiva, muitas vezes superando o TuRBO em dimensões baixas a médias e igualando-o em dimensões altas.
  • vs. Métodos baseados em Penalidade (PEI, EIMI, KB): O SSEI supera consistentemente esses métodos, que sofrem com a degradação do modelo conforme o tamanho do lote cresce.
• Generalização: A abordagem de subespaço foi aplicada com sucesso ao Probability of Improvement (SSPI) e Upper Confidence Bound (SSUCB), mostrando ganhos de desempenho semelhantes sobre seus equivalentes multi-ponto (qPI, qUCB).

Significância e Alegações

O artigo afirma que as Funções de Aquisição de Subespaço propostas fornecem uma solução simples, eficiente e escalável para a otimização bayesiana em lote. A principal significância reside em permitir o uso de recursos de computação paralela de larga escala (grande $q$) sem os gargalos computacionais ou a degradação de precisão associados aos métodos existentes.

Os autores enfatizam que:

• O método mitiga efetivamente a maldição da dimensionalidade na otimização da função de aquisição.
• Oferece um equilíbrio prático entre exploração global (via seleção de subespaço aleatório) e explotação local (via fixação de variáveis não selecionadas).
• É uma extensão "plug-and-play" que pode ser aplicada a várias funções de aquisição e é particularmente valiosa para problemas de otimização caros onde a avaliação paralela é viável.

O trabalho conclui que selecionar pontos de consulta de múltiplos subespaços diferentes é uma estratégia promissora para a otimização bayesiana em lote de larga escala, oferecendo melhorias significativas na velocidade de convergência e na qualidade da solução em comparação com as abordagens atuais de estado da arte.