Establishing an $\Omega(\sqrt{d})$ complexity lower bound for PDMP samplers and how to break it: a sub-$\sqrt{d}$ algorithm for Gaussian-tailed targets

Resumen Técnico: Establecimiento de un Límite Inferior de Complejidad $\Omega(\sqrt{d})$ para Muestreadores PDMP y un Algoritmo Sub-$\sqrt{d}$ para Objetivos de Cola Gaussiana

Planteamiento del Problema
Los muestreadores de Procesos de Markov Deterministas por Partes (PDMP), como el Bouncy Particle Sampler (BPS) y el proceso Zig-Zag, ofrecen una alternativa no reversible a los métodos tradicionales de Monte Carlo por Cadenas de Markov (MCMC). Sin embargo, a pesar de su atractivo teórico, ningún PDMP existente ha demostrado una escala de complejidad computacional mejor que $O(\sqrt{d})$ con respecto a la dimensión del objetivo $d$. En contraste, los métodos basados en gradiente reversibles como Hamiltonian Monte Carlo (HMC) y el Metropolis-Adjusted Langevin Algorithm (MALA) logran escalas superiores de $O(d^{1/4})$ y $O(d^{1/3})$, respectivamente. La cuestión central abordada en este trabajo es si la barrera de $O(\sqrt{d})$ es una limitación inherente del marco de trabajo PDMP o simplemente una consecuencia de diseños algorítmicos específicos.

Metodología
El artículo emplea un enfoque de dos vertientes: una prueba de límite inferior teórica y la construcción de un nuevo algoritmo que relaja los supuestos estándar.

1. Límite Inferior Teórico:
   El autor establece un límite inferior $\Omega(\sqrt{d})$ en la complejidad computacional para una amplia clase de muestreadores PDMP locales. La prueba se basa en varios supuestos estructurales:

   • Independencia del Objetivo: El flujo determinista y el espacio auxiliar no dependen de la distribución objetivo $\pi$ específica.
   • Saltos Locales: El núcleo de salto cambia la variable auxiliar pero no la posición espacial, asegurando trayectorias espaciales absolutamente continuas.
   • Invarianza: La distribución objetivo debe permanecer invariante en todos los tiempos continuos, no solo en los puntos de muestreo discretos.

   Al analizar distribuciones objetivo i.i.d., la prueba demuestra que la tasa de salto esperada $\mathbb{E}[\lambda]$ debe escalar como $\Omega(\sqrt{d})$ para satisfacer la ecuación estacionaria $L^*\mu = 0$. Dado que la distancia entre muestras efectivamente independientes crece como $\sqrt{d}$, y la velocidad promedio está acotada, el número total de saltos requeridos por cada muestra independiente escala como $\Omega(\sqrt{d})$.

2. Innovación Algorítmica (Rompiendo la Barrera):
   Para sortear este límite, el artículo propone relajar el supuesto de que la densidad del objetivo debe ser invariante en todos los tiempos continuos. En su lugar, el algoritmo permite que el objetivo sea invariante solo en los tiempos de muestreo discretos, de manera similar al MCMC estándar.

   • Marco de Trabajo: El método integra el marco Metropolised NUTS-PDMP con una novedosa dinámica de PDMP Oscilante inspirada en la integración leapfrog de HMC.
   • Dinámica: El proceso alterna entre actualizaciones de posición ($\dot{x} = v$) y actualizaciones de velocidad ($\dot{v} = -\nabla U(x)$) en tiempos continuos aleatorios, en lugar de intervalos fijos.
   • Reponderación de la Trayectoria: Dado que la trayectoria continua no preserva estrictamente la medida del objetivo, el algoritmo emplea una estrategia de reponderación de la trayectoria. Este genera una trayectoria utilizando aproximaciones numéricas de las tasas de eventos y luego remuestrea un estado de la trayectoria basándose en una densidad de probabilidad condicional. Esta densidad repondera los estados para corregir las fluctuaciones hamiltonianas a lo largo de la trayectoria, asegurando que el resultado final sea una muestra exacta del objetivo.
   • Adaptatividad: El algoritmo utiliza el criterio No-U-Turn (NUTS) para determinar adaptativamente las longitudes de las trayectorias y emplea tamaños de paso localmente adaptativos para las actualizaciones de velocidad, evitando la necesidad de estrategias complejas de ajuste global requeridas por el HMC reversible.

Contribuciones Clave

• Límite Inferior de Complejidad: El artículo proporciona una prueba rigurosa de que los muestreadores PDMP estándar, que imponen la invariancia en tiempo continuo, están fundamentalmente limitados a una complejidad $\Omega(\sqrt{d})$ para objetivos i.i.d.
• Algoritmo Sub-$\sqrt{d}$: Se introduce un nuevo algoritmo de PDMP metropolizado que renuncia a la invariancia en tiempo continuo. Al utilizar la reponderación de la trayectoria y aproximaciones numéricas, logra una complejidad computacional de $O(d^\alpha)$ donde $\alpha \in [0.2, 0.3]$ para objetivos de cola gaussiana.
• Adaptatividad Local: El marco propuesto incorpora naturalmente la adaptatividad local tanto en la longitud de la trayectoria como en la distancia entre las actualizaciones de velocidad, una característica difícil de implementar en HMC reversible sin estrategias complejas.

Resultados Empíricos
El autor presenta resultados de escalamiento empírico para dimensiones $d \in \{2, \dots, 128\}$ a través de cinco distribuciones objetivo:

• Objetivos de Cola Gaussiana: Para la Gaussiana estándar, la Regresión Logística Bayesiana y los objetivos de Mezcla Gaussiana, el número de eventos por Tamaño de Muestra Efectiva (ESS) escala entre $O(d^{0.22})$ y $O(d^{0.29})$. El número de evaluaciones de gradiente escala entre $O(d^{0.26})$ y $O(d^{0.31})$. Estos resultados superan significativamente el límite de $O(\sqrt{d})$ de los PDMPs tradicionales y se acercan al escalamiento teórico de HMC.
• Objetivos No-Gaussianos: El algoritmo demuestra robustez en distribuciones de cola más pesada (Logística) y más ligera (Cuártica), aunque los exponentes de escalamiento son mayores ($O(d^{0.43})$ a $O(d^{0.64})$), lo que refleja la mayor dificultad de estos objetivos.

Significancia y Reivindicaciones
El artículo afirma identificar una limitación fundamental en el marco de trabajo PDMP estándar: el requisito de invariancia en tiempo continuo es el principal cuello de botella que impide un mejor escalamiento dimensional. Al relajar esta restricción, el autor demuestra que los PDMP pueden lograr un escalamiento sub-$\sqrt{d}$, cerrando la brecha de rendimiento con HMC. El trabajo sugiere que el rendimiento "sub-$\sqrt{d}$" no es un artefacto de un diseño específico, sino una consecuencia de permitir que el muestreador opere con una invariancia aproximada corregida mediante reponderación de Metropolis-Hastings. El autor concluye que, si bien se establece el límite inferior teórico para los PDMP estándar, el algoritmo propuesto ofrece una vía práctica hacia la eficiencia en altas dimensiones, particularmente para objetivos de cola gaussiana, manteniendo al mismo tiempo las ventajas no reversibles de los PDMP.