Resumen Técnico: BAXUS – Optimización Bayesiana Adaptativa en Subespacios Anidados

Enunciado del Problema

La optimización bayesiana de alta dimensión (HDBO) tiene como objetivo optimizar funciones de caja negra costosas de evaluar con decenas hasta cientos de dimensiones de entrada. Aunque los avances recientes han ampliado el alcance de la optimización bayesiana (BO) a campos como las ciencias de la vida, la búsqueda de arquitecturas neuronales y la robótica, los métodos más avanzados enfrentan limitaciones significativas a medida que aumenta la dimensionalidad.

Los enfoques existentes generalmente se dividen en dos categorías, ambas con inconvenientes críticos:

1. Métodos de Región de Confianza (p. ej., TURBO): Estos optimizan sobre regiones acotadas locales (regiones de confianza) dentro del espacio de entrada completo. Aunque son efectivos para dimensiones moderadas, su rendimiento se degrada en dimensiones muy altas porque las regiones de confianza mantienen la dimensionalidad completa del problema, sufriendo la maldición de la dimensionalidad.
2. Métodos de Incrustación Lineal (p. ej., REMBO, HESBO, ALEBO): Estos asumen la existencia de un "subespacio activo" de baja dimensión y proyectan el espacio de entrada de alta dimensión en un espacio objetivo de menor dimensión. Sin embargo, estos métodos requieren que el usuario "adivine" la dimensionalidad efectiva ($d_e$) del subespacio activo. Si la dimensionalidad objetivo elegida ($d$) es demasiado pequeña, el subespacio no puede representar el óptimo global; si $d$ es demasiado grande, la optimización se ralentiza debido a la maldición de la dimensionalidad. Además, métodos como HESBO dependen de una hash aleatoria que ofrece garantías peores para contener un óptimo en comparación con otras incrustaciones.

El desafío central es desarrollar un método HDBO que encuentre de manera fiable óptimos globales sin requerir conocimiento previo de la dimensionalidad del subespacio activo, evitando al mismo tiempo la degradación del rendimiento asociada a los espacios de búsqueda de alta dimensión.

Metodología: BAXUS

Los autores proponen BAXUS (Optimización Bayesiana con subespacios que se expanden adaptativamente), un enfoque fundamentado teóricamente que ajusta dinámicamente la dimensionalidad del espacio de optimización.

1. Subespacios Anidados Adaptativos

En lugar de fijar la dimensionalidad objetivo, BAXUS opera sobre una familia de subespacios aleatorios anidados. El algoritmo comienza con un espacio objetivo de baja dimensión ($d_{init}$) y aumenta progresivamente la dimensionalidad a medida que recopila más datos.

• Inicialización: BAXUS comienza con una dimensión objetivo pequeña $d_0$.
• Expansión: A medida que avanza la optimización, la dimensionalidad objetivo se aumenta "dividiendo" las dimensiones objetivo existentes. Este proceso continúa hasta que la dimensionalidad objetivo alcanza aproximadamente la dimensionalidad de entrada $D$ o se agota el presupuesto de evaluaciones.
• Retención de Observaciones: Una característica crítica de BAXUS es su capacidad para retener observaciones de espacios de menor dimensión al expandirse a dimensiones superiores. Cuando una dimensión objetivo se divide, las dimensiones de entrada contribuyentes se reasignan a la dimensión original y a nuevos contenedores (bins). Los valores de la función (observaciones) se copian a las nuevas dimensiones, asegurando que los datos recopilados en la fase de baja dimensión permanezcan válidos en la fase de mayor dimensión.

2. La Incrustación Escasa de BAXUS

BAXUS utiliza una incrustación lineal escasa novedosa para mapear el espacio objetivo $Y \in \mathbb{R}^d$ al espacio de entrada $X \in \mathbb{R}^D$.

• Estructura: La matriz de incrustación $S^\top \in \{0, \pm 1\}^{d \times D}$ es escasa, lo que significa que cada columna (dimensión de entrada) tiene exactamente una entrada no nula.
• Equilibrio de Contenedores: A diferencia de HESBO, que asigna dimensiones de entrada a dimensiones objetivo de manera uniforme al azar (lo que conduce a tamaños de contenedores variables), BAXUS impone que el número de dimensiones de entrada contribuyentes por dimensión objetivo (tamaño del contenedor) difiera en a lo sumo uno. Esta asignación "equilibrada" se logra permutando las dimensiones de entrada y dividiéndolas en $d$ contenedores.
• Ventaja Teórica: Los autores demuestran que esta incrustación escasa equilibrada proporciona una probabilidad de éxito en el peor caso estrictamente mayor (la probabilidad de que el espacio objetivo contenga un óptimo global) que la incrustación HESBO para dimensiones de entrada finitas. A medida que $D \to \infty$, la probabilidad de éxito de BAXUS converge a la de HESBO.

3. Estrategia de Región de Confianza y División

BAXUS integra la expansión de la incrustación con un enfoque de Región de Confianza (TR) similar a TURBO:

• Regiones de Confianza: La optimización ocurre dentro de regiones de confianza hiperrectangulares en el espacio objetivo, escaladas por las escalas de longitud de los Procesos Gaussianos (GP).
• Disparador de Expansión: La dimensionalidad objetivo se aumenta cuando la longitud del lado base de la región de confianza cae por debajo de un umbral mínimo (lo que indica que la región actual es demasiado pequeña o que el algoritmo está estancado).
• Control de Fallos: El número de "fallos" permitidos (iteraciones consecutivas sin mejora) antes de que ocurra una división se reduce según la dimensionalidad objetivo actual. Esto asegura que el algoritmo pueda alcanzar dimensionalidades altas dentro de un presupuesto de evaluaciones fijo.
• Convergencia: Se demuestra que el algoritmo logra convergencia global. Una vez que la dimensionalidad objetivo alcanza la dimensionalidad de entrada $D$, BAXUS se comporta como TURBO, que se sabe que converge globalmente.

Contribuciones Clave

1. Desarrollo de Algoritmos: Los autores presentan BAXUS, que logra de manera fiable soluciones excelentes en un amplio conjunto de tareas de alta dimensión, superando a los métodos actuales más avanzados.
2. Teoría de Incrustación Novel: Presentan una nueva familia de incrustaciones aleatorias anidadas con tres propiedades clave:
   • Proporciona una garantía peyorativa mayor para contener un óptimo global en comparación con la incrustación HESBO.
   • Es una incrustación escasa óptima, lo que significa que ninguna otra incrustación escasa tiene una mayor probabilidad de éxito en el peor caso para las mismas dimensionalidades de entrada, objetivo y efectiva.
   • Su probabilidad de contener un óptimo converge a la probabilidad de HESBO a medida que la dimensionalidad de entrada $D \to \infty$.
3. Evaluación Exhaustiva: El artículo proporciona evidencia empírica extensa que demuestra la superioridad de BAXUS sobre TURBO, SAASBO, ALEBO, HESBO, CMA-ES y la búsqueda aleatoria en diversas pruebas de referencia.

Resultados Experimentales

Los autores evaluaron BAXUS en una colección de tareas de optimización de hiperparámetros de 388 dimensiones, problemas de diseño de 124 dimensiones y pruebas de referencia con subespacios activos conocidos (LASSO, MOPTA08, BRANIN, HARTMANN).

• Rendimiento: BAXUS superó consistentemente a los métodos más avanzados. En la prueba de referencia SVM de 388D, BAXUS se adaptó a la dimensionalidad objetivo apropiada y encontró mejores soluciones más rápido que TURBO y CMA-ES. En la prueba de referencia LASSO-HARD de 1000D, BAXUS logró soluciones considerablemente mejores que todos los competidores, incluidos los métodos que dependen de suposiciones de subespacio activo (SAASBO, ALEBO, HESBO), los cuales no lograron beneficiarse de la estructura del subespacio activo.
• Robustez: BAXUS demostró robustez frente al ruido observacional, manteniendo un rendimiento sólido en variantes ruidosas de las pruebas de referencia donde competidores como SAASBO y CMA-ES se degradaron significativamente.
• Estudios de Ablación: Reemplazar la incrustación de BAXUS con una incrustación HESBO anidada resultó en un rendimiento significativamente peor, confirmando que la estrategia de contenedores equilibrados es un motor clave del éxito.
• Comparación con Incrustaciones Fijas: BAXUS superó a la ejecución de TURBO con una dimensionalidad objetivo fija, mostrando que la estrategia de expansión adaptativa es superior a las elecciones estáticas de $d$.

Significado y Afirmaciones

El artículo afirma que BAXUS aborda las limitaciones críticas de los métodos HDBO actuales al eliminar la necesidad de que los practicantes "adivinen" la dimensionalidad efectiva del problema. Al expandir adaptativamente el espacio de búsqueda, BAXUS aprovecha la eficiencia de la optimización de baja dimensión mientras garantiza que el espacio de búsqueda eventualmente cubra todo el espacio de entrada, asegurando así que el óptimo global sea alcanzable.

Los autores afirman que BAXUS es un optimizador "listo para usar" (fuera de la caja) que logra un rendimiento robusto en una amplia variedad de tareas de alta dimensión sin requerir suposiciones específicas sobre la estructura del problema (como subespacios activos alineados con los ejes). El trabajo tiene como objetivo hacer que la optimización bayesiana de alta dimensión sea más accesible y fiable para aplicaciones en ciencia e industria donde el número de parámetros ajustables es grande y su dimensionalidad efectiva es desconocida.