Resumo Técnico: Otimização de Caixa-Preta Mista-Categórica via Decomposição Bilevel de Geometria da Informação

Definição do Problema

O artigo aborda a Otimização de Caixa-Preta Mista-Categórica (MC-BBO), uma classe de problemas onde a função objetivo $f(c, x)$ deve ser minimizada sobre um domínio heterogêneo composto por variáveis categóricas $c$ e variáveis contínuas $x$. Especificamente, o estudo foca no caso onde $c$ consiste em variáveis categóricas discretas (modeladas como vetores one-hot ou bits binários) e $x \in \mathbb{R}^{d_x}$.

O desafio central identificado é a presença de fortes interações categórico-contínuas. As abordagens de Estado da Arte (SOTA) de Estratégia Evolutiva (ES) existentes, como CatCMA e ICatCMA, modelam a distribuição de busca como um produto de uma Gaussiana multivariada (para $x$) e uma distribuição categórica (para $c$). Essa suposição de distribuição de produto impõe implicitamente a independência entre $c$ e $x$, impedindo que esses métodos aprendam dependências complexas onde a configuração contínua ótima depende fortemente da escolha categórica. Embora existam métodos Bayesianos, eles frequentemente sofrem com problemas de escalabilidade em espaços de alta dimensão.

Metodologia: IGBD

Os autores propõem a Decomposição Bilevel de Geometria da Informação (IGBD), um framework que modela explicitamente a dependência entre variáveis categóricas e contínuas ao reformular o problema como uma tarefa de otimização bilevel:

$$\min_{c} f(c, x^\star) \quad \text{sujeito a} \quad x^\star = \arg\min_{x} f(c, x)$$

O método emprega a Otimização de Geometria da Informação (IGO) para formular relaxações estocásticas para ambos os níveis da hierarquia:

1. Nível Superior (Otimização Categórica):

   • Otimiza o vetor de probabilidade $q$ que governa a distribuição categórica.
   • Utiliza o método do Gradiente Natural Estocástico Adaptativo (ASNG).
   • Atualiza $q$ ao longo do gradiente natural usando modelagem de fitness baseada em ranking para garantir invariância a transformações monotônicas.
   • Adapta o tamanho do passo (raio de confiança) usando um mecanismo de adaptação de tamanho de passo cumulativo (CSA) análogo ao CMA-ES.

2. Nível Inferior (Otimização Contínua):

   • Otimiza as variáveis contínuas $x$ condicionadas a uma configuração categórica fixa $c$.
   • Utiliza o dd-CMA-ES (uma variante diagonal com atualização ativa) para minimizar a função objetivo $f(c, x)$.
   • O solver de nível inferior é tratado como um processo com estado que fornece uma estimativa do $x^\star(c)$ ótimo para o nível superior.

3. Estratégia de Warm-Starting (Mecanismo de Cache):

   • Para mitigar o custo computacional proibitivo de resolver o problema de nível inferior até a convergência para cada candidato de nível superior, o IGBD introduz uma estratégia de warm-starting.
   • Um cache de $N_\omega$ configurações de nível inferior $\{(x_k, \omega_k, p_k)\}$ é mantido, onde $\omega_k$ representa os parâmetros do CMA-ES e $p_k$ é um escore de qualidade.
   • Seleção: Para cada candidato de nível superior $c_i$, o algoritmo seleciona a melhor configuração em cache $k^\star_i$ baseada no valor objetivo atual.
   • Inicialização: O solver de nível inferior para $c_i$ é inicializado com os parâmetros da configuração de cache selecionada.
   • Atualização: Após a busca de nível inferior, o cache é atualizado. As entradas selecionadas são atualizadas com o novo estado do solver e seus escores são incrementados; as entradas não selecionadas têm seus escores decrementados. Entradas que caem abaixo de um limite são reinicializadas aleatoriamente para promover a exploração.

Principais Contribuições

1. Framework IGBD: A proposta de um framework de otimização bilevel para MC-BBO onde cada nível é uma relaxação estocástica sob IGO. Isso captura explicitamente as interações categórica-contínua que os métodos de distribuição de produto perdem.
2. Novo Tipo de Interação: A introdução de um quarto tipo de interação (Tipo-IV) onde as variáveis categóricas governam as interações dentro do próprio domínio contínuo (por exemplo, alterando a estrutura de covariância ou a rotação do landscape contínuo), além de determinar a localização ótima.
3. Benchmarking: Avaliação abrangente contra CatCMA e ICatCMA em domínios binário-contínuos, incluindo tipos de interação existentes (I, II, III) e o novo Tipo-IV proposto, através de dimensões variadas ($d_c=d_x=5$ e $10$) e forças de interação.

Resultados Experimentais

Os experimentos demonstram que o IGBD supera as abordagens existentes ao lidar com fortes interações, mantendo a eficiência computacional:

• Tratamento de Interação: O IGBD alcança uma taxa de sucesso de 100% em quase todos os tipos e forças de interação testados, incluindo as desafiadoras interações do Tipo-IV, onde CatCMA e ICatCMA falham significativamente.
  • CatCMA: Desempenha-se bem apenas quando as interações são fracas ou ausentes (a suposição de independência se mantém). Falha nas interações de Tipo-III e Tipo-IV conforme a força da interação aumenta.
  • ICatCMA: Melhora o desempenho sobre o CatCMA em interações de Tipo-II (mapeamento afim) devido à sua hiper-representação, mas falha em interações de Tipo-III (máscara não linear) e Tipo-IV. Seu desempenho degrada-se bruscamente conforme a complexidade da interação cresce.
• Eficiência Computacional:
  • O IGBD é geralmente mais eficiente que o ICatCMA, que incorre em altos custos devido aos parâmetros de sua hiper-representação afim.
  • Embora o CatCMA seja mais rápido em problemas simples (interações fracas), o IGBD torna-se mais robusto e eficiente conforme a força da interação ($a$) aumenta, evitando os ciclos massivos de reinicialização e as taxas de falha observadas nos baselines.
• Escalabilidade: O método proposto mantém altas taxas de sucesso em dimensões mais altas ($d=10$), enquanto os baselines lutam significativamente, particularmente com interações do Tipo-IV.

Significância e Alegações

O artigo afirma que o IGBD representa um avanço significativo na otimização de caixa-preta de variáveis mistas ao abordar a limitação fundamental das suposições de independência nas Estratégias Evolutivas atuais. Ao alavancar uma estrutura bilevel com princípios de geometria da informação e um cache de warm-starting, o método modela efetivamente dependências complexas entre variáveis discretas e contínuas.

Os autores observam que, embora a implementação atual seja restrita ao domínio binário-contínuo, a abordagem se estende naturalmente para a otimização categórica mista geral. Eles reconhecem que o alto custo computacional do método em regimes de interação extrema deve-se principalmente ao orçamento de avaliação da função, e não a uma falha algorítmica fundamental. Sugere-se como trabalho futuro a extensão para categorias não binárias, o tratamento de subespaços de baixa dimensão efetiva e a integração de heurísticas de menor custo para aliviar ainda mais o ônus da otimização bilevel.