Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization

Resumo Técnico: Aprendizado para Avaliar a Confiabilidade da Estimativa do Número de Execuções em Otimização Estocástica

Enunciado do Problema
A comparação em larga escala de algoritmos de otimização estocástica enfrenta uma tensão fundamental entre a confiabilidade experimental e a eficiência computacional. Embora execuções repetidas sejam necessárias para uma avaliação válida do desempenho, o custo de repetições extensas cresce rapidamente com a escala dos portfólios de algoritmos e as dimensões dos problemas. As práticas atuais dependem de escolhas de design estáticas (por exemplo, fixar o número de execuções em 15, 25 ou 50), o que assume implicitamente um comportamento homogêneo dos algoritmos entre os problemas — uma suposição raramente sustentada por evidências empíricas.

Trabalhos recentes introduziram uma heurística online empírica que estima adaptativamente o número necessário de execuções por instância, monitorando a estabilidade do desempenho e a simetria da distribuição. Embora esse método melhore a eficiência ao reduzir o total de execuções em aproximadamente 50%, ele sofre de uma limitação crítica: em um subconjunto de casos (desvio de 5–25%), a contagem de execuções estimada é imprecisa. Essas imprecisões só podem ser detectadas retrospectivamente após a conclusão de todas as execuções, tornando o método inadequado para cenários de comparação totalmente online onde a tomada de decisão em tempo real é necessária.

Metodologia
Este estudo propõe uma extensão baseada em aprendizado à heurística online empírica existente, transformando-a em um sistema de autoavaliação capaz de detecção precoce de estimativas de número de execuções não confiáveis.

• Fonte de Dados e Anotação: O estudo utiliza um conjunto de dados derivado de 132.000 execuções de 11 algoritmos de otimização (do framework Nevergrad) em 24 classes de problemas com 20 dimensões (conjunto de benchmarks COCO). Os rótulos de verdade fundamental (estimativas confiáveis vs. não confiáveis) foram estabelecidos por meio de análise post-hoc dos experimentos originais de parada adaptativa, que utilizaram três métodos de detecção de outliers (IQR, poda percentil, escore z modificado) e quatro limiares de assimetria (0,05, 0,10, 0,15, 0,20).
• Extração de Características: Para permitir o aprendizado supervisionado, sequências de comprimento variável de valores da função objetivo são transformadas em vetores de características de dimensão fixa. Um total de 23 características é extraído, categorizado como:
  • Estatísticas: Média, mediana, desvio padrão, variância, quartis, intervalo interquartil, MAD, coeficiente de variação.
  • Distribucionais: Assimetria, curtose, entropia.
  • Relacionadas à Energia: Soma, soma dos valores absolutos, energia do sinal, raiz quadrada da média dos quadrados.
  • Forma e Estabilidade: Inclinação da melhoria do desempenho, desvio padrão rolante, energia FFT e autocorrelação.
• Tarefa de Aprendizado: O problema é formulado como uma tarefa de classificação binária para prever se uma estimativa de número de execuções está correta (1) ou incorreta (0).
  • Desequilíbrio de Classes: O conjunto de dados exibe forte desequilíbrio de classes. O estudo prioriza a detecção de estimativas incorretas (classe minoritária) para evitar paradas prematuras.
  • Seleção de Modelo: A otimização de hiperparâmetros é realizada usando o Optuna em modelos baseados em árvores e ensembles (Árvores de Decisão, Florestas Aleatórias, XGBoost, LightGBM, CatBoost). A função objetivo maximiza o Recall0 (recuperação da classe minoritária) em vez de acurácia ou pontuação F1, pois os falsos negativos (prever uma estimativa não confiável como confiável) são mais prejudiciais do que os falsos positivos.
  • Configuração Experimental: É empregada uma configuração de aprendizado "dentro da configuração". Os modelos são treinados e testados em dados que compartilham o mesmo otimizador, método de detecção de outliers e limiar de assimetria. Isso resulta em 132 conjuntos de dados distintos (3 métodos × 4 limiares × 11 algoritmos).

Principais Contribuições

1. Reenquadramento da Parada Adaptativa: O artigo desloca o foco de meramente estimar o número de execuções para avaliar a confiabilidade dessa estimativa em tempo real.
2. Engenharia de Características para Dinâmica de Otimização: Introduz um conjunto específico de 23 características estatísticas, livres de energia e de forma/estabilidade, derivadas de trajetórias de otimização para caracterizar o comportamento de convergência.
3. Estratégia de Classificação Desbalanceada: Demonstra uma abordagem específica para lidar com dados desbalanceados em contextos de comparação, onde o custo de perder uma estimativa não confiável (falso negativo) supera o custo de execuções redundantes (falso positivo).

Resultados
A avaliação revela desafios significativos e sucessos específicos no aprendizado de confiabilidade dentro de configurações fixas:

• Generalização Limitada: Classificadores válidos (atendendo a $F1_1 > 0,70$ e $Recall_0 > 0,80$) foram obtidos em apenas 48,5% das 132 configurações (64/132). Isso destaca a dificuldade de aprender modelos confiáveis quando restritos a um único otimizador e parâmetros experimentais fixos.
• Variabilidade do Algoritmo: A previsibilidade variou significativamente por algoritmo. Evolução Diferencial (DE), CMA Diagonal, NGOpt14 e NGOpt38 alcançaram as maiores taxas de sucesso (66,7% de configurações válidas), enquanto o NaiveIsoEMNA foi o mais difícil de prever (8,3% de configurações válidas).
• Compromisso com a Linha de Base: Quando comparado a uma linha de base de classe majoritária (que prevê todas as instâncias como confiáveis), os classificadores treinados frequentemente tiveram desempenho inferior em termos de $F1_1$ (apenas 6,8% dos conjuntos de dados superaram a linha de base). No entanto, a linha de base alcançou um $Recall_0$ de 0,00, o que significa que falhou completamente em identificar estimativas não confiáveis. Em contraste, os classificadores treinados consistentemente alcançaram valores de $Recall_0$ acima de 0,80, identificando com sucesso casos problemáticos de convergência que a linha de base perdeu.

Significado e Alegações
O artigo afirma que a confiabilidade do número de execuções pode ser aprendida em um cenário dentro da configuração, permitindo a detecção de estimativas não confiáveis com alta recuperação da classe minoritária. Essa capacidade transforma a heurística adaptativa em um sistema que apoia decisões experimentais em tempo real, preservando os benefícios de eficiência da estimativa adaptativa de execuções.

No entanto, os autores são modestos quanto ao escopo dessas descobertas. Eles afirmam explicitamente que o desempenho é "limitado pela diversidade restrita de dados dentro de configurações fixas". Com apenas 240 instâncias por configuração, os modelos lutam para aprender além da previsão da classe majoritária. O estudo conclui que, embora a previsão de confiabilidade seja possível, ela permanece desafiadora em cenários com dados limitados, sugerindo que trabalhos futuros devem explorar cenários onde dados de diferentes algoritmos de otimização são combinados para aumentar a diversidade de treinamento.