Adaptive Candidate Point Thompson Sampling for High-Dimensional Bayesian Optimization

O artigo apresenta o Adaptive Candidate Thompson Sampling (ACTS), um método que melhora a otimização bayesiana em espaços de alta dimensão ao gerar pontos candidatos adaptativamente em subespaços guiados pelo gradiente do modelo, contornando a esparsidade exponencial das discretizações fixas tradicionais.

O essencial

Imagine que você é um explorador tentando encontrar o ponto mais alto de uma montanha misteriosa, mas você não tem um mapa e não pode ver o topo. Você só pode subir um pouco, olhar ao redor, anotar a altura e decidir para onde ir a seguir. Isso é basicamente o que a Otimização Bayesiana faz: ela tenta encontrar o "melhor" resultado (o topo da montanha) com o menor número de tentativas possível.

O problema é que, se essa montanha tiver milhares de dimensões (em vez de apenas altura e largura), o espaço se torna tão vasto que é como procurar uma agulha em um universo de palheiros. É aí que entra o método tradicional chamado Thompson Sampling.

O Problema: A "Malha" Muito Fina

O Thompson Sampling funciona assim: ele cria uma "montanha imaginária" baseada no que já descobriu e sorteia um ponto aleatório dessa montanha para explorar.

Para fazer isso, ele precisa jogar uma "rede" (uma malha de pontos de teste) sobre a montanha.

• Em 2D: Você pode jogar uma rede com 10.000 pontos e cobrir bem a área.
• Em 1.000 dimensões: Para cobrir a mesma densidade, você precisaria de mais pontos do que existem átomos no universo! A rede fica cheia de buracos gigantes. O método sorteia um ponto, mas a chance de cair em um buraco (longe do topo) é enorme. É como tentar acertar um alvo jogando dardos em um estádio vazio.

A Solução: O "Filtro Inteligente" (ACTS)

Os autores deste paper, Donney Fan e Geoff Pleiss, criaram uma nova técnica chamada ACTS (Amostragem de Thompson com Pontos Candidatos Adaptativos).

Aqui está a analogia simples:

Imagine que você está no pé da montanha (o ponto atual). O método antigo jogava a rede aleatoriamente por toda a montanha. O ACTS faz algo mais esperto:

1. Sente o vento (O Gradiente): Antes de jogar a rede, o ACTS "sente" para onde o vento sopra mais forte (o gradiente). Ele olha para a montanha imaginária e pergunta: "Se eu subir um pouco, para onde a inclinação me leva?"
2. Reduz a área de busca: Em vez de jogar a rede em toda a montanha, ele joga a rede apenas em uma pequena área inclinada na direção que o vento aponta.
3. Aumenta a densidade: Como a área de busca é agora minúscula (um cone estreito apontando para cima), ele pode colocar muito mais pontos na rede dentro dessa pequena área.

A Mágica:
Ao focar apenas na direção promissora, ele consegue colocar uma "malha super densa" em um lugar onde é muito provável que exista um pico. Ele não perde tempo jogando dardos no chão plano ou descendo a montanha.

Por que isso é genial?

1. Não é apenas "local": Você poderia pensar: "Ah, mas ele só olha para perto de onde está, e se o topo estiver longe?". O segredo é que a "montanha imaginária" que o computador cria é aleatória. Às vezes, o vento sopra para o norte, às vezes para o sul. Com o tempo, o método explora todas as direções possíveis, garantindo que ele eventualmente encontre o topo global, não apenas um pico pequeno perto de onde começou.
2. É como um GPS que aprende: Em vez de tentar mapear todo o mundo de uma vez (o que é impossível), ele usa o que sabe agora para focar nos bairros mais promissores, explorando-os com muito mais detalhe.

Resumo da Ópera

• O Velho Jeito: Tentar cobrir um oceano inteiro com uma rede de pesca. A rede é tão frouxa que os peixes (os melhores pontos) passam direto.
• O Novo Jeito (ACTS): O peixeiro olha para a correnteza, percebe que os peixes estão indo para o norte, e joga uma rede super densa e apertada apenas naquela direção. Ele pega muito mais peixes com o mesmo esforço.

Essa técnica permite que computadores otimizem problemas complexos (como desenhar novos medicamentos ou ajustar robôs) que antes eram impossíveis de resolver porque o espaço de busca era grande demais. É como transformar uma busca cega em uma busca guiada por intuição matemática.

Resumo técnico

1. O Problema: A Maldição da Dimensionalidade na Amostragem de Thompson

A Otimização Bayesiana (BO) é um framework eficiente para otimizar funções "caixa-preta" caras e sem derivadas, amplamente utilizado em aprendizado de máquina, descoberta científica e robótica. A Amostragem de Thompson (TS) é uma função de aquisição popular que equilibra exploração e exploração amostrando uma função do modelo substituto (geralmente um Processo Gaussiano - GP) e selecionando o ponto que maximiza essa amostra.

No entanto, a aplicação de TS com GPs em alta dimensão enfrenta um obstáculo fundamental:

• Intratabilidade Contínua: Amostragem de um caminho contínuo de um GP é computacionalmente impossível.
• Discretização Esparsa: A prática comum é amostrar em um conjunto finito de pontos candidatos. Para cobrir adequadamente um espaço de alta dimensão, o número de pontos necessários cresce exponencialmente com a dimensão ($d$).
• Limitação Computacional: Mesmo com aproximações escaláveis, orçamentos computacionais típicos (ex: 10.000 pontos) tornam-se extremamente esparsos em dimensões altas (ex: >100), falhando em capturar os máximos locais ou globais da amostra do GP.

Métodos existentes tentam mitigar isso usando subespaços aleatórios (como RAASP) ou regiões de confiança (TuRBO), mas muitas vezes não conseguem garantir uma densidade suficiente de pontos candidatos nas regiões mais promissoras.

2. Metodologia: Adaptive Candidate Thompson Sampling (ACTS)

O artigo propõe o ACTS, uma abordagem que aumenta a densidade de pontos candidatos não expandindo o número total de pontos, mas reduzindo adaptivamente o espaço de busca durante a amostragem.

Ideia Central

Em vez de fixar um conjunto de candidatos antes de amostrar o GP, o ACTS gera os candidatos condicionados à amostra do gradiente do modelo. A intuição é que o máximo de uma amostra do GP provavelmente estará na direção do gradiente ascendente a partir do ponto atual (incumbente).

O Algoritmo (Resumo)

1. Amostragem do Gradiente: Dado o modelo GP atual $p(f|D_t)$, amostra-se o gradiente no ponto incumbente $x_0$, ou seja, $\nabla f(x_0) \sim p(\nabla f(x_0) | D_t)$.
2. Definição do Espaço de Busca Adaptativo: Constrói-se um subespaço $T_{\nabla f(x_0)}$ alinhado com o gradiente amostrado. O papel define este espaço como um cone alinhado aos eixos (axis-aligned cone) que se estende a partir de $x_0$ na direção do gradiente:
   $$T_{\nabla f(x_0)} = \{x_0 + v \odot \nabla f(x_0) \mid 0 \preceq v \in \mathbb{R}^d\} \cap \mathcal{X}$$
   Onde $\odot$ é o produto elemento a elemento. Isso reduz drasticamente o volume do espaço de busca (ex: em 100 dimensões, o volume pode ser reduzido por um fator de $2^{100}$).
3. Geração de Candidatos: Os pontos candidatos $\tilde{X}$ são gerados dentro deste cone reduzido usando uma política base (como Sobol ou RAASP), mas agora com uma densidade muito maior devido ao espaço menor.
4. Amostragem Conjunta: Amostra-se o valor da função $f(\tilde{X})$ condicionado ao gradiente amostrado e aos dados observados. Isso garante que a amostra do GP seja válida e coerente com a direção de ascensão.
5. Seleção: O próximo ponto a ser avaliado é o máximo da amostra dentro deste conjunto denso de candidatos.

Integração com RAASP

O ACTS pode ser combinado com políticas existentes. Por exemplo, ao usar RAASP (que perturba apenas algumas dimensões), o ACTS modifica a máscara binária para favorecer dimensões onde o gradiente amostrado é maior, aumentando a probabilidade de perturbar nas direções mais promissoras.

3. Contribuições Chave

1. Novo Paradigma de Amostragem: Introduz a ideia de que o conjunto de pontos candidatos não precisa ser independente da amostra do GP. A adaptação baseada no gradiente permite uma discretização muito mais densa nas regiões relevantes.
2. Garantia de Consistência Global: O artigo prova teoricamente (Teorema 1) que, apesar de restringir a busca a um subespaço local baseado em gradientes, o ACTS mantém a consistência global. Como o gradiente é uma amostra aleatória (e não o gradiente verdadeiro), o algoritmo eventualmente explorará todo o espaço e encontrará o ótimo global.
3. Compatibilidade e "Plug-and-Play": O ACTS é um substituto direto ("drop-in replacement") para métodos de TS existentes. Ele funciona bem tanto em configurações globais quanto quando combinado com métodos locais como TuRBO (Trust Regions).
4. Eficiência Computacional: A complexidade assintótica permanece $O(M^3)$ (onde $M$ é o número de candidatos), similar ao TS padrão, pois o custo adicional de amostrar o gradiente e condicionar a distribuição é linear ou quadrático em relação à dimensão, sendo desprezível comparado à decomposição de Cholesky do GP.

4. Resultados Experimentais

Os autores avaliaram o ACTS em diversos benchmarks sintéticos e do mundo real, variando de 12 a 1000 dimensões.

• Desempenho em Dimensões Médias e Altas: O ACTS superou consistentemente métodos de base como RAASP, Amostragem de Thompson Cilíndrica (CTS) e Amostragem de Thompson por Caminho (Pathwise) em tarefas como Lunar Lander, Robot Pushing, Rover, MOPTA08 e ajuste de hiperparâmetros de SVM.
• Comparação com SOTA: Em benchmarks de alta dimensão (até 1000D), o ACTS igualou ou superou métodos de última geração como SAASBO, BAxUS e LogEI.
• Otimização em Lote (Batch): O método demonstrou eficácia em cenários paralelos (batch), mantendo a diversidade das amostras e o desempenho superior.
• Análise de Densidade: A redução do volume do espaço de busca pelo ACTS é massiva (ex: $10^{-18}$ do volume original em 60D), permitindo que os $10^4$ pontos candidatos cubram a região de interesse com muito mais fidelidade do que métodos que espalham os pontos por todo o domínio.
• Qualidade da Amostra: O ACTS produz máximos de amostras do GP ($\max f(x)$) significativamente maiores do que outros métodos, o que se traduz diretamente em melhores valores da função objetivo.

5. Significado e Conclusão

O trabalho de Fan e Pleiss oferece uma solução elegante para o problema de escalabilidade da Amostragem de Thompson em alta dimensão. Ao invés de tentar cobrir o espaço todo com mais pontos (o que é computacionalmente proibitivo), o ACTS foca a amostragem nas regiões onde o máximo é mais provável de estar, utilizando informações locais (gradientes amostrados) de forma inteligente.

Impacto Principal:

• Permite o uso de TS, que possui fortes garantias teóricas de convergência, em problemas de otimização de alta dimensão onde antes era necessário recorrer a heurísticas menos fundamentadas.
• Demonstra que a combinação de informação local (gradiente) com aleatoriedade global (amostragem de GP) pode superar métodos puramente locais (como TuRBO) ou puramente globais (como RAASP padrão).
• É uma contribuição prática imediata para pesquisadores e engenheiros que utilizam otimização bayesiana em problemas complexos de aprendizado de máquina e ciência de dados.

Em resumo, o ACTS transforma a "maldição da dimensionalidade" da discretização em uma vantagem, utilizando a geometria do gradiente amostrado para criar uma malha de busca densa e adaptativa.