Resumen Técnico: Optimización de Caja Negra de Categorías Mixtas mediante Descomposición Bilevel de Geometría de la Información

Definición del Problema

El artículo aborda la Optimización de Caja Negra de Categorías Mixtas (MC-BBO), una clase de problemas donde la función objetivo $f(c, x)$ debe minimizarse sobre un dominio heterogneo que comprende variables categóricas $c$ y variables continuas $x$. Específicamente, el estudio se centra en el caso donde $c$ consiste en variables categóricas discretas (modeladas como vectores one-hot o bits binarios) y $x \in \mathbb{R}^{d_x}$.

El desafío central identificado es la presencia de fuertes interacciones categórico-continuas. Los enfoques actuales de Estrategia Evolutiva (ES) de vanguardia, como CatCMA e ICatCMA, modelan la distribución de búsqueda como un producto de una Gaussiana multivariante (para $x$) y una distribución categórica (para $c$). Esta suposición de distribución de producto impone implícitamente la independencia entre $c$ y $x$, lo que impide que estos métodos aprendan dependencias complejas donde la configuración continua óptima depende fuertemente de la elección categórica. Aunque existen métodos bayesianos, estos suelen sufrir de problemas de escalabilidad en espacios de alta dimensión.

Metodología: IGBD

Los autores proponen la Descomposición Bilevel de Geometría de la Información (IGBD), un marco que modela explícitamente la dependencia entre las variables categóricas y continuas mediante la reformulación del problema como una tarea de optimización bilevel:

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

El método emplea la Optimización de Geometría de la Información (IGO) para formular relajaciones estocásticas para ambos niveles de la jerarquía:

1. Nivel Superior (Optimización Categórica):

   • Optimiza el vector de probabilidad $q$ que rige la distribución categórica.
   • Utiliza el método de Gradiente Natural Estocástico Adaptativo (ASNG).
   • Actualiza $q$ a lo largo del gradiente natural utilizando un modelado de aptitud basado en rangos (rank-based fitness shaping) para asegurar la invarianza ante transformaciones monotónicas.
   • Adapta el tamaño del paso (radio de confianza) utilizando un mecanismo de adaptación de tamaño de paso acumulativo (CSA) análogo a CMA-ES.

2. Nivel Inferior (Optimización Continua):

   • Optimiza las variables continuas $x$ condicionadas a una configuración categórica fija $c$.
   • Utiliza dd-CMA-ES (una variante diagonal con actualización activa) para minimizar la función objetivo $f(c, x)$.
   • El resolvedor de nivel inferior es tratado como un proceso con estado que proporciona una estimación de la $x^\star(c)$ óptima al nivel superior.

3. Estrategia de Arranque en Caliente (Mecanismo de Caché):

   • Para mitigar el costo computacional prohibitivo de resolver el problema de nivel inferior hasta la convergencia para cada candidato de nivel superior, IGBD introduce una estratega de arranque en caliente (warm-starting).
   • Se mantiene una caché de $N_\omega$ configuraciones de nivel inferior $\{(x_k, \omega_k, p_k)\}$, donde $\omega_k$ representa los parámetros de CMA-ES y $p_k$ es una puntuación de calidad.
   • Selección: Para cada candidato de nivel superior $c_i$, el algoritmo selecciona la mejor configuración de la caché $k^\star_i$ basada en el valor de la función objetivo actual.
   • Inicialización: El resolvedor de nivel inferior para $c_i$ se inicializa con los parámetros de la entrada de caché seleccionada.
   • Actualización: Tras la búsqueda de nivel inferior, la caché se actualiza. Las entradas seleccionadas se refrescan con el nuevo estado del resolvedor y sus puntuaciones se incrementan; las entradas no seleccionadas ven sus puntuaciones decrementadas. Las entradas que caen por debajo de un umbral se reinicializan aleatoriamente para promover la exploración.

Contribuciones Clave

1. Marco IGBD: La propuesta de un marco de optimización bilevel para MC-BBO donde cada nivel es una relajación estocástica bajo IGO. Esto captura explícitamente las interacciones categórico-continuas que los métodos de distribución de producto omiten.
2. Nuevo Tipo de Interacción: La introducción de un cuarto tipo de interacción (Tipo-IV) donde las variables categóricas gobiernan las interacciones dentro del propio dominio continuo (por ejemplo, cambiando la estructura de covarianza o la rotación del paisaje continuo), además de determinar la ubicación óptima.
3. Evaluación Comparativa (Benchmarking): Evaluación exhaustiva contra CatCMA e ICatCMA en dominios binario-continuos, incluyendo los tipos de interacción existentes (I, II, III) y el nuevo Tipo-IV propuesto, a través de diversas dimensionalidades ($d_c=d_x=5$ y $10$) e intensidades de interacción.

Resultados Experimentales

Los experimentos demuestran que IGBD supera a los métodos existentes en el manejo de interacciones fuertes manteniendo la eficiencia computacional:

• Manejo de Interacciones: IGBD logra una tasa de éxito del 100% en casi todos los tipos y fuerzas de interacción probados, incluyendo las desafiantes interacciones de Tipo-IV donde CatCMA e ICatCMA fallan significativamente.
  • CatCMA: Funciona bien solo cuando las interacciones son débiles o ausentes (la suposición de independencia se cumple). Falla en las interacciones de Tipo-III y Tipo-IV a medida que aumenta la fuerza de la interacción.
  • ICatCMA: Mejora respecto a CatCMA en interacciones de Tipo-II (mapeo afín) debido a su hiper-representación afín, pero falla en las interacciones de Tipo-III (máscara no lineal) y Tipo-IV. Su rendimiento se degrada drásticamente a medida que crece la complejidad de la interacción.
• Eficiencia Computacional:
  • IGBD es generalmente más eficiente que ICatCMA, el cual incurre en altos costos debido a sus parámetros de hiper-representación afín.
  • Aunque CatCMA es más rápido en problemas simples (interacciones débiles), IGBD se vuelve más robusto y eficiente a medida que la fuerza de la interacción ($a$) aumenta, evitando los masivos ciclos de reinicio y las tasas de fallo observadas en los modelos base.
• Escalabilidad: El método propuesto mantiene altas tasas de éxito en dimensiones superiores ($d=10$), mientras que los modelos base presentan dificultades significativas, particularmente con las interacciones de Tipo-IV.

Significado y Reivindicaciones

El artículo sostiene que IGBD representa un paso significativo hacia adelante en la optimización de caja negra de variables mixtas al abordar la limitación fundamental de las suposiciones de independencia en las Estrategias Evolutivas actuales. Al aprovechar una estructura bilevel con principios de geometría de la información y una caché de arranque en caliente, el método modela eficazmente las dependencias complejas entre variables discretas y continuas.

Los autores señalan que, aunque la implementación actual está restringida al dominio binario-continuo, el enfoque se extiende naturalmente a la optimización categórica mixta general. Reconocen que el alto costo computacional del método en regímenes de interacción extrema se debe principalmente al presupuesto de evaluación de la función y no a un fallo algorítmico fundamental. Se sugiere como trabajo futuro la extensión a categorías no binarias, el manejo de subespacios de baja dimensión efectiva y la integración de heurísticas de menor costo para aliviar aún más la carga de la optimización bilevel.