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

Resumen Técnico: Aprendizaje para Evaluar la Fiabilidad de la Estimación del Número de Ejecuciones en la Optimización Estocástica

Planteamiento del Problema
La evaluación comparativa a gran escala de algoritmos de optimización estocástica enfrenta una tensión fundamental entre la fiabilidad experimental y la eficiencia computacional. Si bien las ejecuciones repetidas son necesarias para una evaluación válida del rendimiento, el costo de una repetición extensa crece rápidamente con la escala de los portafolios de algoritmos y las dimensiones del problema. Las prácticas actuales dependen de decisiones de diseño estáticas (por ejemplo, fijar el número de ejecuciones en 15, 25 o 50), lo que asume implícitamente un comportamiento homogéneo de los algoritmos entre problemas, una suposición rara vez respaldada por evidencia empírica.

Trabajos recientes introdujeron una heurística en línea empírica que estima de forma adaptativa el número de ejecuciones requerido por instancia mediante el monitoreo de la estabilidad del rendimiento y la simetría de la distribución. Si bien este método mejora la eficiencia al reducir las ejecuciones totales en aproximadamente un 50%, adolece de una limitación crítica: en un subconjunto de casos (desviación del 5–25%), la cantidad de ejecuciones estimada es inexacta. Estas inexactitudes solo pueden detectarse retrospectivamente una vez completadas todas las ejecuciones, lo que hace que el método sea inadecuado para escenarios de evaluación comparativa totalmente en línea donde se requiere la toma de decisiones en tiempo real.

Metodología
Este estudio propone una extensión basada en aprendizaje para la heurística en línea empírica existente, transformándola en un sistema de autoevaluación capaz de la detección temprana de estimaciones del número de ejecuciones poco fiables.

• Fuente de Datos y Anotación: El estudio utiliza un conjunto de datos derivado de 132.000 ejecuciones de 11 algoritmos de optimización (del marco Nevergrad) a través de 24 clases de problemas en 20 dimensiones (suite de evaluación comparativa COCO). Las etiquetas de verdad fundamental (estimaciones fiables frente a no fiables) se establecieron mediante un análisis post-hoc de los experimentos originales de parada adaptativa, los cuales utilizaron tres métodos de detección de valores atípicos (RIC, recorte percentílico, puntuación z modificada) y cuatro umbrales de asimetría (0,05; 0,10; 0,15; 0,20).
• Extracción de Características: Para habilitar el aprendizaje supervisado, las secuencias de longitud variable de los valores de la función objetivo se transforman en vectores de características de dimensión fija. Se extrae un total de 23 características, categorizadas como:
  • Estadísticas: Media, mediana, desviación estándar, varianza, cuartiles, rango intercuartílico, MAD, coeficiente de variación.
  • Distribucionales: Asimetría, curtosis, entropía.
  • Relacionadas con la energía: Suma, suma de valores absolutos, energía de la señal, raíz cuadrática media.
  • Forma y Estabilidad: Pendiente de la mejora del rendimiento, desviación estándar móvil, energía FFT y autocorrelación.
• Tarea de Aprendizaje: El problema se formula como una tarea de clasificación binaria para predecir si una estimación del número de ejecuciones es correcta (1) o incorrecta (0).
  • Desequilibrio de Clases: El conjunto de datos presenta un fuerte desequilibrio de clases. El estudio prioriza la detección de estimaciones incorrectas (clase minoritaria) para evitar una parada prematura.
  • Selección del Modelo: La optimización de hiperparámetros se realiza utilizando Optuna en modelos basados en árboles y ensembles (Árboles de Decisión, Bosques Aleatorios, XGBoost, LightGBM, CatBoost). La función objetivo maximiza la Recall0 (recuperación de la clase minoritaria) en lugar de la precisión o la puntuación F1, ya que los falsos negativos (predecir una estimación poco fiable como fiable) son más perjudiciales que los falsos positivos.
  • Configuración Experimental: Se emplea una configuración de aprendizaje "dentro de la configuración". Los modelos se entrenan y prueban en datos que comparten el mismo optimizador, método de valores atípicos y umbral de asimetría. Esto resulta en 132 conjuntos de datos distintos (3 métodos × 4 umbrales × 11 algoritmos).

Contribuciones Clave

1. Reencuadre de la Parada Adaptativa: El artículo desplaza el enfoque de meramente estimar el número de ejecuciones a evaluar la fiabilidad de dicha estimación en tiempo real.
2. Ingeniería de Características para la Dinámica de Optimización: Introduce un conjunto específico de 23 características estadísticas, libres de energía y de forma/estabilidad derivadas de las trayectorias de optimización para caracterizar el comportamiento de convergencia.
3. Estrategia de Clasificación con Desequilibrio: Demuestra un enfoque específico para manejar datos desequilibrados en contextos de evaluación comparativa, donde el costo de pasar por alto una estimación poco fiable (falso negativo) supera el costo de las ejecuciones redundantes (falso positivo).

Resultados
La evaluación revela desafíos significativos y éxitos específicos en el aprendizaje de la fiabilidad dentro de configuraciones fijas:

• Generalización Limitada: Se obtuvieron clasificadores válidos (cumpliendo $F1_1 > 0,70$ y $Recall_0 > 0,80$) en solo el 48,5% de las 132 configuraciones (64/132). Esto resalta la dificultad de aprender modelos fiables cuando se restringen a un único optimizador y parámetros experimentales fijos.
• Variabilidad del Algoritmo: La predictibilidad varió significativamente según el algoritmo. La Evolución Diferencial (DE), CMA Diagonal, NGOpt14 y NGOpt38 lograron las tasas de éxito más altas (66,7% de configuraciones válidas), mientras que NaiveIsoEMNA fue el más difícil de predecir (8,3% de configuraciones válidas).
• Compensación con la Línea Base: En comparación con una línea base de clase mayoritaria (que predice todas las instancias como fiables), los clasificadores entrenados a menudo rindieron peor en términos de $F1_1$ (solo el 6,8% de los conjuntos de datos superó a la línea base). Sin embargo, la línea base logró una $Recall_0$ de 0,00, lo que significa que falló completamente en identificar estimaciones poco fiables. Por el contrario, los clasificadores entrenados lograron consistentemente valores de $Recall_0$ superiores a 0,80, identificando con éxito casos de convergencia problemáticos que la línea base pasó por alto.

Significado y Afirmaciones
El artículo afirma que la fiabilidad del número de ejecuciones puede aprenderse en un escenario dentro de la configuración, permitiendo la detección de estimaciones poco fiables con una alta recuperación de la clase minoritaria. Esta capacidad transforma la heurística adaptativa en un sistema que apoya las decisiones experimentales en tiempo real mientras preserva los beneficios de eficiencia de la estimación adaptativa de ejecuciones.

Sin embargo, los autores son modestos sobre el alcance de estos hallazgos. Afirman explícitamente que el rendimiento está "limitado por la diversidad de datos restringida dentro de las configuraciones fijas". Con solo 240 instancias por configuración, los modelos luchan por aprender más allá de la predicción de la clase mayoritaria. El estudio concluye que, aunque la predicción de fiabilidad es posible, sigue siendo un desafío en entornos con datos limitados, lo que sugiere que el trabajo futuro debería explorar escenarios donde se combinen datos de diferentes algoritmos de optimización para aumentar la diversidad de entrenamiento.