A Profile-Separation Framework for Quantitative Convergence of No-U-Turn Samplers

Resumen Técnico: Un Marco de Separación de Perfiles para la Convergencia Cuantitativa de los Muestreadores No-U-Turn

Planteamiento del Problema
El Hamiltoniano Monte Carlo (HMC) genera propuestas distantes mediante la simulación de trayectorias hamiltonianas, pero su eficiencia depende críticamente del tiempo de integración. Las trayectorias demasiado cortas producen un movimiento mínimo, mientras que las demasiado largas retrastean regiones ya visitadas, desperdiciando computación. El No-U-Turn Sampler (NUTS) aborda esto construyendo de forma adaptativa una órbita de leapfrog y terminándola cuando los diagnósticos de los puntos finales indican un "U-turn" (vectores de momento apuntando de regreso hacia el inicio). Aunque NUTS es central para el éxito práctico de los sistemas de programación probabilística (por ejemplo, Stan, PyMC), su regla de parada recursiva y dependiente del estado ha obstaculizado históricamente el desarrollo de una teoría de mezcla cuantitativa. Los límites no asintóticos existentes para NUTS se han basado mayoritariamente en estructuras objetivo gaussianas, donde los diagnósticos aleatorios de U-turn se concentran alrededor de una función seno determinista. Extender estos resultados a objetivos generales fuertemente log-cóncavos sigue siendo un desafío significativo debido a la dependencia conjunta de la transición con el refresco del momento, las decisiones de duplicación aleatorias, los errores numéricos de energía y la regla de selección específica.

Metodología
Este artículo introduce un Marco de Separación de Perfiles para establecer la convergencia cuantitativa para variantes multinomiales y de progresión sesgada de NUTS en objetivos $(m, L)$-fuertemente log-cóncavos que satisfacen la regularidad de la Hessiana de Frobenius. La metodología central consiste en desacoplar el mecanismo de parada adaptativo del análisis de mezcla mediante los siguientes pasos:

1. Perfil de U-Turn Estacionario: El autor define un objeto determinista a nivel de población, el perfil estacionario $u(t) = \mathbb{E}[V_0^\top (X_t - X_0)]$, que representa la media de equilibrio de los diagnósticos de punto final utilizados por NUTS. Para objetivos generales, esto reemplaza las funciones seno gaussianas explícitas.
2. Separación de Perfil: Se introduce una condición suficiente donde una profundidad específica $k^*$ está "separada de perfil". Esto requiere que el perfil $u(t)$ sea uniformemente positivo en todas las duraciones diádicas pre-terminales y uniformemente negativo en la duración terminal candidata, con un margen de orden $d/\sqrt{m}$.
3. Estabilidad del Diagnóstico Intrínseco: El marco cuantifica la desviación entre los diagnósticos numéricos prácticos (basados en leapfrog) y el perfil de población exacto. Esto implica acotar:
   • La concentración de los diagnósticos escalares exactos alrededor de $u(t)$.
   • El error numérico del leapfrog en estos diagnósticos.
   • El fallo de las ventanas de energía uniformes.
   • El fallo de positividad en intervalos muy cortos.
4. Certificación de Profundidad Terminal: Bajo la suposición de que el margen de separación de perfil excede los errores estocásticos y numéricos combinados, el autor demuestra que, en un evento de alta probabilidad, cada realización de las decisiones de duplicación aleatoria termina en la misma cardinalidad $K^*$ mediante un U-turn genuino, estrictamente antes del límite de profundidad máxima.
5. Transferencia de Profundidad Terminal a Conductancia: Una vez certificada una profundidad terminal y una ventana de energía comunes, se muestra que la transición NUTS contiene una mezcla explícita de propuestas de leapfrog de índice fijo. El autor utiliza la simetría del punto inicial de la duplicación aleatoria y las identidades de equilibrio detallado para construir operadores positivos (proyecciones ortogonales para multinomial, esqueletos de dos pasos para la progresión sesgada) que permiten la aplicación de la isoperimetría de Cheeger para derivar límites de conductancia restringidos.

Contribuciones Clave

1. Certificado de Parada Independiente del Objetivo: El artículo abstrae el mecanismo de perfil determinista de los análisis gaussianos hacia la "separación de perfil", una condición aplicable a objetivos generales fuertemente log-cóncavos. Esto proporciona un certificado intrínseco que transfiere los signos a cada órbita completa y subárbol recursivo inspeccionado por el árbol de leapfrog práctico.
2. Teorema de Profundidad Terminal a Conductancia: Un nuevo teorema establece que, una vez certificada una profundidad terminal común, la transición adaptativa de NUTS puede acotarse mediante estimaciones de movimiento de tiempo fijo. Esto separa el problema de la trayectoria (probar dónde se detiene el árbol) del problema de la mezcla (probar que el núcleo cruza los cortes).
3. Operadores Positivos para Kernels No Perezosos: El autor demuestra que los núcleos multinomial y de progresión sesgada originales (sin lazificación artificial) poseen propiedades espectrales positivas. Se muestra que el re-enraizamiento multinomial es una proyección ortogonal, mientras que el esqueleto de dos pasos del núcleo de progresión sesgada es semidefinido positivo, permitiendo argumentos de conductancia sin modificar el muestreador.
4. Análisis General de Trayectoria y Numérico: El trabajo proporciona identidades de equilibrio para perfiles no lineales, desigualdades de desplazamiento de media cuadrática y límites de positividad inicial universal. Establece la concentración de diagnósticos exactos y comparaciones deterministas de leapfrog-a-flujo sin requerir límites sobre el Jacobiano completo del Hamiltoniano.
5. Rutas de Verificación: El artículo ofrece rutas de verificación específicas para el certificado intrínseco, incluyendo representaciones espectrales para productos no lineales, límites perturbativos para objetivos casi isotrópicos y condiciones para la adaptación de métricas para eliminar la anisotropía lineal.

Resultados
El teorema principal (Teorema 3.7) proporciona límites de transición incondicionales para la mezcla de arranque en caliente (warm-start). Sea $T^*$ la longitud de la trayectoria física seleccionada y $a^* = \sqrt{m}T^*$. El número de transiciones $n$ requerido para alcanzar un error de variación total $\epsilon$ está acotado por:

• NUTS Multinomial: $\tilde{O}\left( (1 + a^{*2}\kappa^2(1+\gamma)^{4/3}) \log(M/\epsilon) \right)$
• NUTS de Progresión Sesgada: $\tilde{O}\left( (1 + a^{*4}\kappa^3(1+\gamma)^2) \log(M/\epsilon) \right)$

donde $\kappa = L/m$ es el número de condición y $\gamma$ se relaciona con la regularidad de la Hessiana.

Respecto al trabajo computacional, el artículo distingue entre transiciones certificadas y no certificadas. En el evento de certificación, el costo es proporcional a la profundidad seleccionada $K^*$. Sin restricciones adicionales sobre el límite de profundidad máxima, el límite de trabajo determinista incondicional es proporcional al tope máximo $K_{cap}$. Sin embargo, el autor proporciona límites refinados esperados y de alta probabilidad que interpolan entre $K^*$ y $K_{cap}$, recuperando el orden determinista $K^* n$ cuando el tope es comparable a la profundidad certificada.

Para objetivos gaussianos, el marco recupera la dependencia de la dimensión $\tilde{O}(d^{1/4})$ y caracteriza explícitamente los regímenes de "aceleración" y "atrapamiento" identificados en la literatura previa específica de Gaussianos, mostrando que la separación de perfil recupera la dicotomía de dos escalas.

Significancia y Reivindicaciones
El artículo afirma proporcionar la primera teoría de mezcla cuantitativa para NUTS práctico en objetivos generales fuertemente log-cóncavos que no depende de la estructura gaussiana ni de modificaciones artificiales (como la lazificación o las correcciones de Metropolis). La contribución principal es una reducción de trayectoria a mezcla, demostrando que el mecanismo de parada adaptativo de NUTS práctico se comporta lo suficientemente predecible como para que las estimaciones de tiempo fijo de HMC sean útiles, siempre que el perfil estacionario esté separado de cero por los errores estocásticos y numéricos combinados.

El autor enfatiza que los resultados son globales e incondicionales respecto a los límites de transición, mientras que el trabajo computacional se contabiliza por separado para reflejar la realidad de que las transiciones no certificadas (que corren hasta el tope) siguen siendo parte de la cadena de Markov. El marco valida el uso de métricas de post-calentamiento fijas para eliminar la anisotropía lineal y proporciona una base rigurosa para el éxito empírico de NUTS en entornos de alta dimensión y no gaussianos. El artículo no pretende que la separación de perfil sea necesaria para una mezcla rápida, sino que es una condición suficiente que unifica el análisis de HMC adaptativo a través de una amplia clase de objetivos.