KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

Resumen Técnico: KSOS-BO: Mejora del Muestreo en la Optimización Bayesiana mediante la Suma de Cuadrados de Núcleos

Planteamiento del Problema
La Optimización Bayesiana (BO) es un marco estándar para la optimización global de funciones de caja negra costosas, ampliamente utilizado en el ajuste de hiperparámetros, robótica y diseño científico. El procedimiento de BO implica dos pasos: ajustar un modelo sustituto (típicamente un Proceso Gaussiano) y optimizar una función de adquisición para seleccionar el siguiente punto de consulta. Aunque una investigación significativa se ha centrado en mejorar los modelos sustitutos y el diseño de funciones de adquisición, la optimización de la propia función de adquisición sigue siendo un cuello de botella crítico. En la práctica, este problema de optimización interna suele ser no convexo, multimodal y de alta dimensión. Los optimizadores sin derivadas existentes (por ejemplo, Evolución Diferencial, CMA-ES, Búsqueda Sobol) a menudo tratan esto como un problema genérico de caja negra, fallando en explotar explícitamente la naturaleza estructurada de los paisajes de adquisición. En consecuencia, estos métodos pueden quedar atrapados en óptimos locales o requerir evaluaciones excesivas para encontrar candidatos de alta calidad, limitando la eficiencia general del proceso de BO.

Metodología: KSOS-BO
Los autores proponen KSOS-BO, un marco basado en núcleos y sin derivadas diseñado específicamente para optimizar funciones de adquisición. El método adapta el enfoque de Suma de Cuadrados de Núcleos (KernelSOS) al entorno de BO.

1. Formulación: La idea central es reformular la minimización de la función de adquisición $\alpha(x)$ como un problema de optimización global que busca el mayor límite inferior $c$ tal que $\alpha(x) - c \geq 0$ para todo $x$ en el dominio.
2. Relajación de Núcleos: A diferencia de los métodos clásicos de Suma de Cuadrados (SOS) restringidos a objetivos polinómicos, KSOS-BO utiliza Espacios de Hilbert de Núcleos Reproductores (RKHS). Reemplaza las bases polinómicas de dimensión finita con funciones de núcleo. La restricción de no negatividad se relaja en un programa semidefinido (SDP) que involucra una matriz de núcleo $K$ derivada de un conjunto finito de puntos muestreados.
3. Optimización y Recuperación: El algoritmo resuelve un SDP para encontrar una representación sustituto basada en núcleos de la función de adquisición desplazada. En lugar de optimizar directamente en el espacio de entrada, recupera un punto candidato continuo $x^*$ como una combinación ponderada de los puntos muestreados. Esto permite que el método realice una búsqueda global estructurada utilizando únicamente evaluaciones de función.
4. Integración: En cada iteración de BO, KSOS-BO muestrea puntos para evaluar la función de adquisición actual, construye el sustituto KernelSOS, resuelve el SDP para encontrar el siguiente candidato y actualiza el modelo de BO.

Contribuciones Clave

• Búsqueda Global Estructurada: El artículo introduce una aplicación novedosa de KernelSOS a la optimización de adquisición, avanzando más allá de la búsqueda genérica de caja negra para explotar la naturaleza suave y estructurada de los paisajes de adquisición inducida por los sustitutos de Procesos Gaussianos.
• Marco sin Derivadas: El método opera sin requerir gradientes, lo que lo hace compatible con configuraciones estándar sin derivadas, al tiempo que proporciona una alternativa fundamentada a las búsquedas heurísticas basadas en poblaciones.
• Ganancias de Rendimiento: Los autores demuestran que, a pesar de un mayor costo computacional por iteración debido al paso del SDP, KSOS-BO logra una convergencia más rápida en tiempo de reloj al alcanzar soluciones de alta calidad con menos evaluaciones de adquisición.

Resultados Experimentales
Los autores evaluaron KSOS-BO frente a tres líneas base sin derivadas (Búsqueda Sobol, Evolución Diferencial y CMA-ES) en 15 funciones de referencia con propiedades de paisaje variables (multimodales, en forma de cuenco, en forma de valle, en forma de meseta y con caídas pronunciadas) en 10 dimensiones.

• Mejora del Arrepentimiento: KSOS-BO logró el mejor rendimiento en 10 de 15 referencias. En estas funciones de mejor rendimiento, mostró una mejora promedio del arrepentimiento del 81.16% en comparación con el segundo mejor optimizador.
• Eficiencia en Tiempo de Reloj: Aunque KSOS-BO incurre en una mayor sobrecarga computacional por iteración, convergió más rápido en tiempo real. En las 10 referencias donde ocupó el primer lugar, logró una mejora promedio en el tiempo de reloj del 93.55%, reduciendo efectivamente a la mitad el tiempo requerido para alcanzar la misma precisión que las líneas base.
• Sensibilidad al Paisaje: El método destacó en funciones altamente multimodales (por ejemplo, Ackley, Rastrigin, Griewank) y funciones unimodales suaves (por ejemplo, Rosenbrock, Dixon Price). Sin embargo, el rendimiento se degradó en funciones con curvatura extrema, caídas pronunciadas o regiones en forma de meseta (por ejemplo, Michalewicz, Zakharov, Styblinski Tang), donde se encontró que la representación basada en núcleos era menos adecuada.
• Robustez: Los estudios de ablación indicaron que KSOS-BO es robusto ante variaciones en el tamaño del diseño inicial, presupuestos de evaluación y elecciones de núcleo (Gaussiano vs. Laplace), aunque superó consistentemente a las líneas base en la mayoría de los casos de prueba.

Significado y Afirmaciones
El artículo afirma que mejorar únicamente el paso de optimización de adquisición produce mejoras medibles en el rendimiento general de la Optimización Bayesiana. El significado principal radica en demostrar que tratar la optimización de adquisición como un problema estructurado resoluble mediante relajaciones KernelSOS es superior a tratarlo como un problema genérico de caja negra.

Los autores notan modestamente que, aunque KSOS-BO es efectivo para diversas estructuras de paisaje, no es una solución universal; tiene dificultades con características geométricas específicas como caídas pronunciadas o mesetas planas. Además, el método introduce un compromiso computacional: el paso del SDP es más costoso que las estrategias evolutivas estándar, pero este costo se justifica por la reducción en el número de evaluaciones de función costosas requeridas para encontrar soluciones óptimas. El trabajo sugiere que las direcciones futuras deberían centrarse en mejorar la escalabilidad de KSOS-BO, explorar estrategias híbridas con refinamiento local y probarlo en configuraciones de mayor dimensión o con restricciones.