Cost-aware Stopping for Bayesian Optimization

Resumen Técnico: Parada Consciente del Costo para la Optimización Bayesiana

Planteamiento del Problema
En el aprendizaje automático automatizado, el descubrimiento científico y otras aplicaciones de la optimización bayesiana (BO), los profesionales se enfrentan al desafío de decidir cuándo terminar la evaluación de funciones de caja negra costosas. Aunque existen reglas de parada existentes, estas a menudo no logren considerar de manera fundamentada la variación en los costos de evaluación.

• Reglas heurísticas (por ejemplo, conteos de iteraciones fijos o detenerse cuando el mejor valor permanece sin cambios) carecen de garantías teóricas y pueden detenerse demasiado pronto o incurrir en evaluaciones innecesarias.
• Reglas basadas en el arrepentimiento (regret-based) (por ejemplo, UCB-LCB, Knowledge Gradient) están fundamentadas teóricamente para minimizar el arrepentimiento simple, pero suelen estar diseñadas para entornos de costo uniforme. No consideran explícitamente los costos de evaluación, lo que a menudo conduce a costos acumulados excesivos y a un alto arrepentimiento ajustado por costo cuando los costos son elevados.
• Funciones de adquisición conscientes del costo (por ejemplo, el Índice de Gittins de la Caja de Pandora (PBGI) y la mejora esperada logarítmica por costo (LogEIPC)) se han desarrollado para optimizar el compromiso entre la calidad de la solución y el costo, pero su integración con reglas de parada adaptativas no ha sido estudiada sistemáticamente.

El objetivo central es diseñar una regla de parada que optimice el arrepentimiento simple esperado ajustado por costo, definido como la suma del arrepentimiento simple (la diferencia entre la mejor solución encontrada y el óptimo global) y el costo acumulado de la recolección de datos.

Metodología
Los autores proponen una nueva regla de parada consciente del costo, fundamentada en el marco de decisión de la Caja de Pandora. La metodología establece una conexión teórica entre dos funciones de adquisición conscientes del costo de vanguardia:

1. Índice de Gittins de la Caja de Pandora (PBGI): Derivado de la solución de programación dinámica del problema de la Caja de Pandora, adaptado para la optimización bayesiana correlacionada.
2. Mejora Esperada Logarítmica por Costo (LogEIPC): Una aproximación de un solo paso de la política óptima bayesiana.

La regla de parada propuesta, denominada regla de parada PBGI/LogEIPC, se define por la condición de que la optimización debe cesar cuando ningún punto no observado ofrece una mejora esperada que valga su costo de evaluación. Matemáticamente, la regla se detiene en el tiempo $\tau$ cuando:
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
o equivalentemente:
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
donde $y^*_{1:\tau}$ es el mejor valor observado hasta el momento.

Los detalles clave de la implementación incluyen:

• Sincronización de la Actualización de la Posterior: La regla utiliza los valores de la función de adquisición computados después de la actualización de la posterior de la iteración actual (prospectiva), lo cual los autores argumentan que refleja mejor la intuición de "valor justo" y produce ganancias empíricas sobre los enfoques retrospectivos.
• Manejo de Costos Desconocidos: Cuando los costos son desconocidos, se modelan estocásticamente (por ejemplo, como un Proceso Gaussiano sobre el logaritmo del costo), y se utiliza el costo esperado $E[c(x)]$ en la condición de parada.
• Estabilización: Para evitar paradas espurias causadas por fluctuaciones del modelo o una optimización imperfecta de la función de adquisición (especialmente en dimensiones altas), los autores imponen un periodo de estabilización y aplican un suavizado de media móvil a la señal de parada.

Contribuciones Clave

1. Una Nueva Regla de Parada Consciente del Costo: El artículo presenta una regla de parada adaptativa derivada de la teoría de la Caja de Pandora que se extiende naturalmente al principio de diseño de la mejora esperada. Proporciona un marco unificado aplicable tanto a la BO clásica como a la consciente del costo.
2. Garantías Teóricas: Los autores demuestran que, al combinarse con las funciones de adquisición PBGI o LogEIPC, la regla de parada propuesta satisface un límite superior teórico en el arrepentimiento simple esperado ajustado por costo. Específicamente, se garantiza que la política no funcionará peor que la línea base de "parada inmediata" (detenerse justo después de la primera evaluación). Esta constituye la primera garantía teórica de este tipo para cualquier regla de parada adaptativa en la optimización bayesiana.
3. Validación Empírica: El estudio proporciona una evaluación sistemática a través de tareas sintéticas y referentes empíricos (LCBench para optimización de hiperparámetros y NATS-Bench para búsqueda de arquitectura neuronal).

Resultados

• Tareas Sintéticas: En configuraciones de arrepentimiento bayesiano de 1D y 8D con funciones de costo uniformes, lineales y periódicas, la regla de parada PBGI/LogEIPC, junto con su función de adquisición correspondiente, iguala o supera consistentemente a otros pares (incluyendo UCB-LCB, LogEIPC-med y PRB). Es particularmente robusta en escenarios de alto costo.
• Referentes Empíricos:
  • En LCBench (35 conjuntos de datos), la regla propuesta junto con PBGI o LogEIPC se sitúa en el top 3 para aproximadamente el 75% de las tareas.
  • En NATS-Bench, la regla es competitiva, acercándose al rendimiento óptimo retrospectivo (hindsight-optimal).
  • La regla se detiene de manera confiable antes del límite de iteraciones (200 iteraciones), mientras que las reglas basadas en el arrepentimiento de la línea base (como SRGap-med y UCB-LCB) frecuentemente fallan en detenerse temprano, incurriendo en costos excesivos.
  • Los autores señalan que el bajo rendimiento en ciertos conjuntos de datos pequeños se debe probablemente a desajustes intrínsecos de validación/prueba del referente más que a la regla de parada en sí.

Significancia y Reivindicaciones
El artículo afirma abordar una consideración práctica crítica pero poco explorada en la optimización bayesiana: la determinación consciente del costo de cuándo detenerse.

• Avance Teórico: El trabajo cierra la brecha entre las funciones de adquisición conscientes del costo y la parada adaptativa, proporcionando la primera garantía formal de que una política adaptativa no incurrirá en un arrepentimiento ajustado por costo peor que la parada inmediata.
• Utilidad Práctica: La regla propuesta elimina la necesidad de la sintonización heurística de umbrales de parada (por ejemplo, constantes fijas o umbrales basados en la mediana) al derivar el umbral directamente del costo de evaluación.
• Robustez: El marco demuestra robustez ante diversas estructuras de costo y errores de especificación del modelo, ofreciendo una alternativa fundamentada a los criterios de parada heurísticos en tareas de optimización costosas.

Los autores concluyen que su marco puede extenderse a entornos que involucren evaluaciones ruidosas, de múltiples fidelidades o por lotes (batches), así como a formulaciones de objetivos alternativos, aunque esto se menciona como direcciones futuras y no como contribuciones actuales.