Accelerating Black-Box Bilevel Optimization with Rank-Based Upper-Level Value Function Approximation

Título: Aceleração da Otimização Bilevel de Caixa-Preta com Aproximação de Função de Valor de Nível Superior Baseada em Ranks

1. Problema e Contexto

A otimização bilevel (BLOPs) envolve um problema de otimização aninhado dentro de outro, onde a solução do nível inferior (variáveis $\mathbf{y}$) depende das variáveis do nível superior (variáveis $\mathbf{x}$). A formulação geral busca minimizar uma função objetivo de nível superior $F(\mathbf{x}, \mathbf{y}^*_\mathbf{x})$, sujeita a $\mathbf{y}^*_\mathbf{x}$ ser a solução ótima de um problema de nível inferior $f(\mathbf{x}, \mathbf{y})$.

No cenário de caixa-preta (onde não há informações sobre gradientes ou estrutura analítica), os métodos existentes enfrentam desafios significativos:

• Custo Computacional Elevado: A natureza aninhada exige resolver o problema de nível inferior até a convergência para cada iteração do nível superior.
• Limitações dos Métodos Atuais:
  • Redução para Nível Único: Frequentemente inviável em caixa-preta devido à falta de condições de otimalidade explícitas.
  • Métodos Aninhados (ex: BL-CMA-ES): Sofrem com alto custo computacional e ineficiência na inicialização quando há forte interação entre variáveis.
  • Métodos de Aproximação/Surrogatos: Enfrentam dificuldades de escalabilidade e construção de modelos precisos em paisagens complexas (multimodais, não convexas).

O método anterior mais avançado, BL-CMA-ES, utiliza CMA-ES (Estratégia de Evolução com Adaptação de Matriz de Covariância) em ambos os níveis, mas sofre de quatro limitações principais:

1. Incompatibilidade de Distribuição: Atualiza a distribuição do nível superior com pares refinados $(\mathbf{x}, \hat{\mathbf{y}})$ que diferem dos pares amostrados originalmente, violando premissas do CMA-ES.
2. Inicialização Ineficaz: A marginalização da distribuição para inicializar o nível inferior pode ser enganosa em problemas com forte interação entre variáveis.
3. Perda de Informação: O conhecimento ganho durante a otimização do nível inferior é descartado a cada atualização do nível superior.
4. Falta de Colaboração: Não há mecanismo para compartilhar informações entre solucionadores do nível inferior de candidatos diferentes.

2. Metodologia Proposta: URA-CMA-ES

Os autores propõem o URA-CMA-ES (Upper-Level Ranking Approximation CMA-ES), uma generalização do método WRA-CMA-ES (originalmente para problemas min-max) adaptada para otimização bilevel. A abordagem utiliza uma estrutura aninhada, mas com inovações cruciais para reduzir o custo computacional e aumentar a robustez.

Principais Mecanismos:

• Aproximação de Ranks no Nível Superior:
  Em vez de calcular o valor exato da função objetivo de nível superior para cada candidato, o método aproveita a invariância de algoritmos evolutivos baseados em ranks (como o CMA-ES) a transformações monótonas. O algoritmo aproxima diretamente os ranks da função de valor de nível superior $\Phi(\mathbf{x})$, evitando a necessidade de convergência completa do otimizador de nível inferior para cada iteração.

• Inicialização por "Warm Starting" (Arranque Quente):
  O método mantém um cache de $N_\omega$ configurações (vetor de média e matriz de covariância) de solucionadores do nível inferior de gerações anteriores. Para cada candidato $\mathbf{x}$ do nível superior, seleciona-se a configuração do cache que melhor performou no nível inferior para aquele $\mathbf{x}$ específico.

  • Benefício: Resolve o problema de inicialização ineficaz (Limitação 2) e permite o compartilhamento seletivo de informação entre gerações (Limitação 3), adaptando-se a interações fortes entre variáveis.

• Parada Antecipada (Early Stopping):
  O otimizador de nível inferior executa em "rodadas". Após cada rodada, calcula-se o coeficiente de correlação de rank de Kendall entre os ranks da função de nível superior estimada na rodada atual e na anterior.

  • Critério: Se a correlação exceder um limiar ($\tau_{threshold}$), assume-se que a ordenação dos candidatos não mudará significativamente com mais iterações, e o processo de nível inferior é interrompido.
  • Benefício: Reduz drasticamente o custo computacional do loop interno, evitando convergência desnecessária.

• Processamento Posterior e Atualização do Cache:
  Um mecanismo de pontuação ($p_k$) gerencia o cache. Configurações selecionadas têm sua pontuação aumentada; as não selecionadas são penalizadas. Se a pontuação cair abaixo de um limiar, a configuração é re-inicializada aleatoriamente, garantindo exploração e evitando a propagação de informações irrelevantes.

3. Contribuições Chave

1. Correção da Incompatibilidade de Distribuição: Ao amostrar e atualizar o nível superior baseando-se na mesma função de valor aproximada (ranks), o URA-CMA-ES elimina a discrepância entre a distribuição amostrada e a atualizada, melhorando a convergência em paisagens difíceis.
2. Eficiência Computacional: A combinação de warm starting e early stopping reduz significativamente o número de avaliações de função (FEs) necessárias no nível inferior.
3. Versatilidade em Paisagens Complexas: O método demonstra superioridade em problemas com multimodalidade (múltiplos ótimos locais) e forte interação entre variáveis, cenários onde métodos colaborativos anteriores (como BOC) falham devido à troca indiscriminada de informações.
4. Generalização: O framework é aplicável a qualquer otimizador baseado em ranks, não se limitando estritamente ao CMA-ES.

4. Resultados Experimentais

Os autores avaliaram o URA-CMA-ES em duas suites de benchmarks padrão (SMD e WRA) com dimensões de $(20+20)$, comparando com BL-CMA-ES e BOC (Collaborative Optimization).

• Suite SMD (Otimização Bilevel):

  • O URA-CMA-ES foi o mais robusto, resolvendo a maioria dos problemas onde BL-CMA-ES e BOC falharam (ex: SMD7 e SMD8 com multimodalidade no nível superior).
  • BOC falhou consistentemente em problemas com multimodalidade no nível inferior devido à sua colaboração indiscriminada.
  • Em termos de custo, o URA-CMA-ES exigiu significativamente menos FEs no nível inferior do que os concorrentes, compensando o pequeno overhead no nível superior.

• Suite WRA (Problemas Min-Max):

  • O URA-CMA-ES demonstrou superioridade em problemas com forte interação (termos bilineares) e condicionamento ruim.
  • Métodos concorrentes falharam em problemas onde a resposta ótima do nível inferior correspondia a vértices específicos de um espaço de caixa (devido à inicialização por marginalização ineficaz). O warm starting do URA-CMA-ES permitiu navegar eficientemente por esses vértices.
  • O método foi estatisticamente mais rápido em problemas difíceis (ex: WRA11, mal condicionado) e comparável em problemas bem comportados.

• Estudo de Ablação:

  • A remoção do early stopping aumentou drasticamente o custo computacional e impediu a convergência em alguns casos.
  • A remoção do warm starting (especialmente a troca de informações entre gerações) resultou na falha total em resolver os benchmarks, provando que a preservação de informação histórica é essencial.

5. Significado e Conclusão

O URA-CMA-ES representa um avanço significativo na otimização bilevel de caixa-preta. Ele consegue o "melhor dos dois mundos": a eficiência de métodos colaborativos (como o BOC) sem sacrificar a generalidade e robustez necessárias para lidar com paisagens de otimização complexas e não lineares.

Ao focar na aproximação de ranks e na gestão inteligente de informação (via warm starting e early stopping), o método supera as limitações fundamentais de abordagens anteriores, oferecendo uma solução escalável e robusta para problemas bilevel reais que envolvem interações complexas e múltiplos ótimos locais. O trabalho abre caminho para futuras aplicações em algoritmos evolutivos de variáveis mistas e integração com métodos de busca local especializados.