Resumen Técnico: Eliminar el Proceso de los Procesos Gaussianos del Bucle

Declaración del Problema

La Optimización Bayesiana (BO) se emplea tradicionalmente para problemas de caja negra donde las evaluaciones de la función son costosas, lo que resulta en pocas observaciones ($N$). Sin embargo, una clase creciente de problemas, denominada Optimización Bayesiana con Muchas Observaciones (BOMO), implica evaluaciones rápidas y paralelizables (por ejemplo, simulaciones a gran escala) donde $N$ puede alcanzar decenas de miles.

En el régimen BOMO, los métodos estándar de BO enfrentan un cuello de botella de escalabilidad. Los enfoques tradicionales dependen de sustitutos de Procesos Gaussianos (GP). Aunque las implementaciones modernas han reducido la complejidad temporal de adquisición de $O(N^3)$ a aproximadamente $O(N^2)$, el requisito de ajustar los hiperparámetros del GP en cada iteración sigue siendo una carga computacional significativa. Este proceso de ajuste, que a menudo implica la reconstrucción de la matriz del núcleo, escala mal con $N$, impidiendo la aplicación de BO a problemas con cantidades masivas de observaciones.

Metodología

Los autores proponen TuRBO-ENN, un método que reemplaza el sustituto GP en el marco de Optimización Bayesiana de Región de Confianza (TuRBO) con una alternativa ligera llamada Vecinos Más Cercanos Epistémicos (ENN).

1. Vecinos Más Cercanos Epistémicos (ENN)

ENN es un sustituto basado en K-vecinos más cercanos (KNN) diseñado para estimar tanto los valores de la función como la incertidumbre (epistémica y aléatoria) con una escalabilidad lineal.

• Construcción del Sustituto: Para un punto de consulta $x$, ENN identifica los $K$ vecinos más cercanos en el conjunto de observaciones $D$. Trata a cada vecino como una estimación independiente del valor de la función.
• Cuantificación de la Incertidumbre:
  • Varianza Aléatoria ($\sigma_a^2$): Modelada como la suma de un nivel base de ruido ($s_0^2$) y la escala de ruido específica de la observación ($s_m^2$).
  • Varianza Epistémica ($\sigma_e^2$): Modelada como proporcional al cuadrado de la distancia euclidiana entre el punto de consulta y el vecino ($c_e d^2(x, x_m)$).
• Agregación: La estimación final de la media $\mu(x)$ y las estimaciones de varianza se calculan utilizando un promedio ponderado por precisión (ponderación inversa de la varianza) de los $K$ vecinos. Esto evita los cálculos de covarianza par por par de $O(N^2)$ requeridos por los GP.
• Complejidad: Encontrar los $K$ vecinos más cercanos utilizando una estructura de datos de montículo máximo (max-heap) o la biblioteca Faiss toma $O(N \ln K)$ por consulta. El ajuste de los hiperparámetros ($s_0, c_e$) se realiza mediante Estimación de Máxima Verosimilitud de Tipo II (MLE) sobre una pseudoverosimilitud de Validación Cruzada de Dejar-Uno-Fuera (LOOCV), aproximada utilizando una submuestra de tamaño fijo para mantener una escalabilidad de $O(N)$.

2. Integración TuRBO-ENN

El método integra ENN en el algoritmo TuRBO, que utiliza una región de confianza para centrar los esfuerzos de búsqueda.

• Objetivos Ruidosos: Para problemas con ruido, el método ajusta los hiperparámetros de ENN y utiliza la función de adquisición Límite Superior de Confianza (UCB): $UCB(x) = \mu(x) + \sigma(x)$.
• Objetivos Libres de Ruido: Para problemas deterministas, los autores proponen una variante sin ajuste. Dado que el ajuste de hiperparámetros es innecesario cuando se sabe que el ruido es cero, el método selecciona candidatos mediante Ordenamiento No Dominado (NDS) sobre el par $(\mu(x), \sigma(x))$. Esto elimina por completo el paso de ajuste, reduciendo aún más el tiempo de propuesta.
• Optimización Pseudo-Bayesiana (PBO): Los autores verifican que TuRBO-ENN satisface las condiciones para la Optimización Pseudo-Bayesiana (Chen & Lam, 2025), asegurando garantías teóricas de convergencia.

Contribuciones Clave

1. Sustituto ENN: Introducción de un sustituto KNN ligero que estima valores de función e incertidumbre con tiempos de ajuste y consulta de $O(N)$, en contraste con la escalabilidad de $O(N^2)$ o $O(N^3)$ de los GP.
2. Algoritmo TuRBO-ENN: Desarrollo de un método de BO que reemplaza el GP y el Muestreo de Thompson de TuRBO con ENN y UCB (o NDS para casos libres de ruido).
3. Validación Empírica: Demostración de que TuRBO-ENN reduce el tiempo de propuesta (ajuste + adquisición) en uno o dos órdenes de magnitud en comparación con TuRBO-GP en problemas con hasta 50.000 observaciones, sin sacrificar la calidad de la solución.
4. Garantía Teórica: Verificación de que TuRBO-ENN califica como un método PBO, heredando garantías de convergencia.
5. Código Abierto: Lanzamiento del paquete Python ennbo.

Resultados Experimentales

Los autores compararon TuRBO-ENN con métodos de última generación (TuRBO-GP, Optuna, SMAC, CMA-ES, DNGO, Vecchia GP) en cinco tareas de simulación (LunarLander, Hopper, BipedalWalker, Push) y una tarea de optimización de hiperparámetros (LASSO-DNA) con dimensiones que oscilan entre 12 y 180.

• Escalabilidad: Mientras que los métodos basados en GP (por ejemplo, turbo-one, ucb) exhibieron una escalabilidad aproximada de $O(N^2)$ en el tiempo de propuesta, TuRBO-ENN escaló linealmente ($O(N)$).
• Aceleración: TuRBO-ENN logró aceleraciones que oscilan entre 8.5x y 151x sobre TuRBO-GP, con mayores ganancias observadas en conteos de observaciones más altos ($N$) y en configuraciones de ruido congelado (libres de ruido) donde se omitió el ajuste de hiperparámetros.
• Calidad de la Solución: TuRBO-ENN igualó el rendimiento de optimización (calidad de la solución) de TuRBO-GP en todas las tareas probadas.
• Tareas de Ajuste: En tareas de regresión pura (datos sintéticos), ENN fue órdenes de magnitud más rápido de ajustar que los GP Exactos, SVGP y sustitutos de redes neuronales, manteniendo al mismo tiempo verosimilitudes logarítmicas competitivas en el conjunto de prueba.

Significado y Afirmaciones

El artículo argumenta que, a medida que crecen las capacidades de simulación, el cuello de botella en la Optimización Bayesiana se desplaza del costo de la evaluación de la función al costo computacional del propio algoritmo de optimización (tiempo de propuesta). Al eliminar el Proceso Gaussiano del bucle, TuRBO-ENN permite que BO escale a regímenes con decenas de miles de observaciones donde los métodos tradicionales se vuelven computacionalmente prohibitivos.

Los autores afirman modestamente que su método proporciona una alternativa práctica y escalable para problemas BOMO, ofreciendo una opción "sin ajuste" para simulaciones deterministas y una opción de escalabilidad lineal para las ruidosas, todo mientras mantiene las propiedades teóricas de convergencia de la optimización bayesiana. Señalan que, aunque logran garantías de convergencia a través de los axiomas PBO, no proporcionan límites de arrepentimiento específicos. Las direcciones de trabajo futuro sugeridas incluyen adaptar ENN a algoritmos de vecinos más cercanos aproximados para una escalabilidad de $O(\ln N)$ y explorar la ponderación específica de la dimensión en la métrica de distancia.