Cost-aware Stopping for Bayesian Optimization

Resumo Técnico: Parada Consciente de Custo para Otimização Bayesiana

Enunciado do Problema
Na aprendizagem automática automatizada, na descoberta científica e em outras aplicações de otimização bayesiana (BO), os praticantes enfrentam o desafio de decidir quando interromper a avaliação de funções de caixa-preta caras. Embora existam regras de parada existentes, elas frequentemente falham em considerar os custos de avaliação de maneira fundamentada.

• Regras heurísticas (ex: contagens de iterações fixas ou interrupção quando o melhor valor permanece inalterado) carecem de garantias teóricas e podem interromper o processo cedo demais ou incorrer em avaliações desnecessárias.
• Regras baseadas em regret (ex: UCB-LCB, Knowledge Gradient) são teoricamente fundamentadas para minimizar o regret simples, mas são tipicamente projetadas para configurações de custo uniforme. Elas não consideram explicitamente os custos de avaliação, o que frequentemente leva a custos cumulativos excessivos e a um alto regret ajustado ao custo quando os custos são elevados.
• Funções de aquisição conscientes de custo (ex: Pandora's Box Gittins Index (PBGI) e log expected improvement per cost (LogEIPC)) foram desenvolvidas para otimizar o compromisso entre a qualidade da solução e o custo, mas sua integração com regras de parada adaptativas não foi sistematicamente estudada.

O objetivo central é projetar uma regra de parada que otimize o regret simples ajustado ao custo esperado, definido como a soma do regret simples (a diferença entre a melhor solução encontrada e o ótimo global) e o custo cumulativo da coleta de dados.

Metodologia
Os autores propõem uma nova e fundamentada regra de parada consciente de custo derivada do framework de decisão Pandora's Box. A metodologia estabelece uma conexão teórica entre duas funções de aquisição conscientes de custo de última geração:

1. Pandora's Box Gittins Index (PBGI): Derivado da solução de programação dinâmica do problema Pandora's Box, adaptado para otimização bayesiana correlacionada.
2. Log Expected Improvement per Cost (LogEIPC): Uma aproximação de um passo de tempo único da política ótima bayesiana.

A regra de parada proposta, denominada regra de parada PBGI/LogEIPC, é definida pela condição de que a otimização deve cessar quando nenhum ponto não observado oferece uma melhoria esperada que valha seu custo de avaliação. Matematicamente, a regra para no tempo $\tau$ quando:
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
ou equivalentemente:
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
onde $y^*_{1:\tau}$ é o melhor valor observado até o momento.

Detalhes cruciais de implementação incluem:

• Tempo de Atualização do Posterior: A regra utiliza os valores da função de aquisição computados após a atualização do posterior da iteração atual (prospectiva/forward-looking), o que os autores argumentam que reflete melhor a intuição de "valor justo" (fair value) e produz ganhos empíricos sobre abordagens retrospectivas (backward-looking).
• Tratamento de Custos Desconhecidos: Quando os custos são desconhecidos, eles são modelados estocasticamente (por exemplo, como um Processo Gaussiano no log-custo), e o custo esperado $E[c(x)]$ é usado na condição de parada.
• Estabilização: Para evitar paradas espúrias causadas por flutuações do modelo ou otimização imperfeita da função de aquisição (especialmente em dimensões altas), os autores impõem um período de estabilização e aplicam um suavizamento de média móvel ao sinal de parada.

Principais Contribuições

1. Uma Nova Regra de Parada Consciente de Custo: O artigo apresenta uma regra de parada adaptativa derivada da teoria de Pandora's Box que se estende naturalmente ao princípio de design de melhoria esperada. Ela fornece um framework unificado aplicável tanto à BO clássica quanto à consciente de custo.
2. Garantias Teóricas: Os autores provam que, quando pareada com funções de aquisição PBGI ou LogEIPC, a regra de parada proposta satisfaz um limite superior teórico no regret simples ajustado ao custo esperado. Especificamente, a política é garantida para performar não pior do que a linha de base de "parada imediata" (parar logo após a primeira avaliação). Isto constitui a primeira garantia teórica deste tipo para qualquer regra de parada adaptativa em otimização bayesiana.
3. Validação Empírica: O estudo fornece uma avaliação sistemática através de tarefas sintéticas e benchmarks empíricos (LCBench para otimização de hiperparâmetros e NATS-Bench para busca de arquitetura neural).

Resultados

• Tarefas Sintéticas: Em configurações de regret bayesiano 1D e 8D com funções de custo uniformes, lineares e periódicas, a regra de parada PBGI/LogEIPC, pareada com sua respectiva função de aquisição, consistentemente iguala ou supera outros pares (incluindo UCB-LCB, LogEIPC-med e PRB). É particularmente robusta em cenários de alto custo.
• Benchmarks Empíricos:
  • No LCBench (35 datasets), a regra proposta pareada com PBGI ou LogEIPC classifica-se entre os 3 melhores em aproximadamente 75% das tarefas.
  • No NATS-Bench, a regra performa de forma competitiva, aproximando-se do desempenho ótimo hindsight.
  • A regra interrompe confiavelmente antes do limite de iterações (200 iterações), enquanto as regras de regret baseadas em linhas de base (como SRGap-med e UCB-LCB) frequentemente falham em interromper precocemente, incorrendo em custos excessivos.
  • Os autores observam que o desempenho inferior em datasets específicos pequenos deve-se provavelmente a desalinhamentos intrínsecos de validação/teste do benchmark, e não à própria regra de parada.

Significância e Alegações
O artigo afirma abordar uma consideração prática crítica, porém subexplorada, na otimização bayesiana: a determinação consciente de custo de quando parar.

• Avanço Teórico: O trabalho preenche a lacuna entre funções de aquisição conscientes de custo e a parada adaptativa, fornecendo a primeira garantia formal de que uma política adaptativa não incorrerá em um regret ajustado ao custo pior do que a parada imediata.
• Utilidade Prática: A regra proposta elimina a necessidade de ajuste heurístico de limiares de parada (ex: constantes fixas ou limiares baseados na mediana) ao derivar o limiar diretamente do custo de avaliação.
• Robustez: O framework demonstra robustez através de variadas estruturas de custo e erros de especificação de modelo, oferecendo uma alternativa fundamentada aos critérios de parada heurísticos em tarefas de otimização caras.

Os autores concluem que seu framework pode ser estendido para cenários envolvendo avaliações ruidosas, de múltiplas fidelidades ou em lote (batched), bem como para formulações de objetivos alternativas, embora estas sejam mencionadas como direções futuras e não como contribuições atuais.