Optimally-Weighted Herding is Bayesian Quadrature

Planteamiento del Problema
Un desafío fundamental en el aprendizaje automático estadístico es el cálculo de las expectativas de funciones sobre distribuciones de probabilidad, expresadas como $Z_{f,p} = \int f(x)p(x)dx$. Mientras que los métodos de Monte Carlo aproximan esto mediante el muestreo aleatorio con una tasa de convergencia de $O(1/\sqrt{N})$, estos sufren de varianza estocástica. Los métodos de Quasi-Monte Carlo ofrecen una alternativa determinista generando pseudo-muestras para minimizar la discrepancia entre la distribución empírica de las muestras y la distribución objetivo $p(x)$. Dos métodos deterministas prominentes son el Kernel Herding, que minimiza la Discrepancia Media Máxima (MMD) para seleccionar muestras, y la Cuadratura Bayesiana (BQ), que infiere una distribución posterior sobre la función integrando $f$ para estimar la integral. El artículo aborda la conexión teórica entre estos dos métodos e investiga si un enfoque ponderado de la selección de muestras puede superar al Herding estándar.

Metodología
Los autores establecen un vínculo teórico entre el Kernel Herding y la Cuadratura Bayesiana analizando las funciones objetivo que cada uno minimiza.

1. Equivalencia de Criterios: El artículo demuestra que el criterio minimizado en el Kernel Herding (MMD) es matemáticamente equivalente a la varianza posterior de la estimación de la integral en la Cuadratura Bayesiana, asumiendo un proceso gaussiano (GP) sobre $f$. Específicamente, el error esperado en BQ corresponde a la MMD entre la distribución objetivo $p$ y una distribución discreta definida por las muestras y sus pesos.
2. Cuadratura Bayesiana Secuencial (SBQ): Mientras que el Herding estándar asigna pesos uniformes ($1/N$) a las muestras, la BQ asigna pesos óptimos derivados del posterior del GP. Los autores proponen la Cuadratura Bayesiana Secuencial (SBQ), un algoritmo voraz (greedy) que selecciona ubicaciones de muestra para minimizar la varianza posterior (equivalente a minimizar la MMD con pesos óptimos).
3. Análisis de Pesos: El artículo analiza las propiedades de los pesos de la BQ, señalando que no son necesariamente positivos y no suman uno. Se demuestra que estos pesos son óptimos en un sentido minimax sobre el Espacio de Hilbert de Núcleo Reproductor (RKHS) definido por el núcleo.
4. Submodularidad: Los autores investigan las propiedades de convergencia de la SBQ relacionando el proceso de selección con el problema de selección de diccionario disperso. Demuestran que la función objetivo es "aproximadamente submodular", lo que permite establecer límites teóricos sobre el rendimiento de la estrategia de selección voraz, aunque estos límites son más débiles que los de las funciones estrictamente submodulares.

Contribuciones Clave

1. Unificación Teórica: El artículo prueba que la pérdida minimizada por el Kernel Herding es idéntica al error esperado (varianza posterior) en la Cuadratura Bayesiana. En consecuencia, la BQ se enmarca como una versión ponderada del Kernel Herding donde los pesos son óptimos para el RKHS dado.
2. Optimalidad de los Pesos: Se muestra que los pesos derivados de la BQ dominan al Herding de ponderación uniforme y a otros métodos de herding no óptimamente ponderados en términos de tasa de convergencia.
3. Conexión Algorítmica: El trabajo conecta la selección voraz de muestras en BQ con el problema de selección de diccionario disperso, estableciendo que la función objetivo es aproximadamente submodular.
4. Validación Empírica: Los autores proporcionan evidencia empírica demostrando que la SBQ logra una tasa de convergencia más rápida que $O(1/N)$, superando tanto al Herding estándar como al muestreo i.i.d. aleatorio en términos de Discrepancia Media Máxima y error de estimación de la integral.

Resultados

• Tasas de Convergencia: En experimentos utilizando una mezcla de Gaussianas en 2D, la SBQ demostró una tasa de convergencia superior a la tasa $O(1/N)$ típicamente asociada al Herding en espacios de dimensión finita. Aunque la tasa teórica exacta para la SBQ en espacios de dimensión infinita permanece desconocida, los resultados empíricos sugieren que es más rápida que $O(1/N)$.
• Eficiencia de Muestreo: El artículo ilustra cómo un pequeño número de muestras de SBQ (por ejemplo, 8) con pesos óptimos puede lograr el mismo error de estimación que un mayor número de muestras de Herding (por ejemplo, 20) con pesos uniformes.
• Robustez: Los experimentos en funciones fuera del RKHS asumido mostraron que, aunque las garantías teóricas dependen de que la función pertenezca al RKHS, el ranking de rendimiento relativo de los métodos (SBQ > Herding > i.i.d.) se mantuvo consistente incluso para funciones "fuera del modelo".
• Límites de Error: La MMD proporciona un límite superior demostrable sobre el error empírico de la estimación de la BQ, el cual se mostró que disminuye rápidamente con el número de muestras.

Significancia y Reivindicaciones
El artículo afirma que la Cuadratura Bayesiana Secuencial representa un avance significativo sobre el Kernel Herding al integrar la ponderación óptima en el proceso de selección de muestras. Al ver la BQ como un método de Herding ponderado de forma óptima, los autores proporcionan un marco teórico unificado que explica el rendimiento superior de la BQ. El trabajo destaca que, si bien la BQ incurre en un costo computacional más alto ($O(N^3)$ para el cálculo de pesos frente a $O(N^2)$ para Herding), la tasa de convergencia más rápida puede hacerla más eficiente en escenarios donde las evaluaciones de la función son costosas. Los autores señalan modestamente que, aunque establecen un límite superior en el error empírico y demuestran una convergencia más rápida que $O(1/N)$ empíricamente, la tasa de convergencia teóricamente óptima para la SBQ en espacios de dimensión infinita sigue siendo una pregunta abierta para investigaciones futuras. El artículo concluye que la elección del método depende del compromiso entre el costo computacional y el costo de evaluar la función integrando $f$.