Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo

1. Planteamiento del Problema

El objetivo central de la estadística computacional es aproximar esperanzas de la forma $\nu(f) = \int f(x)\nu(dx)$, donde $\nu$ es una distribución objetivo y $f$ es una función integrable. Cuando el muestreo directo es imposible (por ejemplo, debido a constantes de normalización desconocidas), se utilizan métodos MCMC (Monte Carlo mediante Cadenas de Markov).

• MCMC Adaptativo: Permite actualizar el mecanismo de transición de la cadena basándose en su historia completa. Aunque puede mejorar la convergencia, introduce comportamientos no markovianos que complican el análisis teórico.
• El Desafío: La teoría de límites para MCMC adaptativo suele requerir supuestos técnicos fuertes, como la "adaptación decreciente" (diminishing adaptation), para garantizar la convergencia.
• Enfoque del Artículo: Los autores estudian algoritmos MCMC Adaptativos Cada Vez Más Raros (AIR, por sus siglas en inglés). En estos algoritmos, la adaptación no ocurre en cada paso, sino en intervalos de tiempo que se vuelven cada vez más largos. El objetivo es establecer tasas de convergencia casi segura para las sumas de Monte Carlo renormalizadas bajo condiciones más generales que las tradicionales, específicamente utilizando contracciones de tipo Wasserstein.

2. Metodología

Los autores desarrollan un marco teórico basado en los siguientes pilares:

A. Espacio de Estado Aumentado

Siguiendo trabajos recientes (como [PHL20]), el análisis se realiza en un espacio de estado aumentado $\mathcal{Y} = \mathcal{X} \times \Phi$, donde $\Phi$ es un espacio auxiliar.

• Esto permite manejar problemas como la multimodalidad de la distribución objetivo.
• El caso clásico (no aumentado) se recupera como un caso especial donde $\Phi$ es un singleton.

B. Aproximación por Martingalas y Ecuación de Poisson

La técnica principal de demostración es la aproximación por martingalas basada en la solución de la ecuación de Poisson:
$$u_\gamma(y) - P_\gamma u_\gamma(y) = h(y) - \pi_\gamma(h)$$
Donde $P_\gamma$ es el núcleo de transición con parámetro de adaptación $\gamma$.

• La suma de errores de Monte Carlo se descompone en una parte de martingala ($M_n$), un término de residuo ($R_m$) asociado a los momentos de adaptación, y términos de borde.
• Una ventaja clave de los esquemas AIR es que, debido a la rareza de la adaptación, muchos términos del residuo se cancelan o son más fáciles de controlar que en esquemas puramente adaptativos.

C. Contracción de Tipo Wasserstein

En lugar de asumir ergodicidad uniforme o geométrica estándar, los autores introducen una condición de contracción basada en una función similar a la distancia de Wasserstein ($W$).

• Definición: Se utiliza una función "tipo distancia" $d$ (distance-like) para definir una métrica de Wasserstein $W$.
• Supuesto de Contracción (Assumption 3.1): Se asume que existe un coeficiente de contracción $\tau < 1$ tal que la distancia entre las distribuciones de dos cadenas iniciales diferentes se reduce geométricamente bajo la acción del núcleo $P_\gamma$, uniformemente en el parámetro de adaptación $\gamma$.

D. Esquema AIR

Se define una secuencia de tiempos de adaptación $T_m = \sum_{j=1}^m k_j$, donde $k_j \approx j^\beta$.

• Si $\beta \ge 1$, la adaptación es suficientemente rara.
• Si $\beta \in (0, 1)$, la adaptación es más frecuente, lo que complica el análisis del término de residuo.

3. Contribuciones Clave

1. Tasas de Convergencia Casi Segura: El artículo establece que, bajo condiciones de contracción de Wasserstein, las sumas de Monte Carlo renormalizadas convergen a cero casi seguramente. Específicamente, se demuestra:
   $$\lim_{n \to \infty} \frac{1}{r(n)} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{c.s.}$$
   Donde $r(n)$ es un factor de renormalización cercano a $\sqrt{n \log n}$ (similar a la Ley del Logaritmo Iterado).

2. Eliminación de Supuestos Técnicos: A diferencia de la teoría de MCMC adaptativo general, los resultados para esquemas AIR no requieren la suposición de "adaptación decreciente" (diminishing adaptation) ni la continuidad uniforme de los núcleos, siempre que se cumpla la condición de contracción uniforme en el espacio de parámetros.

3. Generalidad del Marco: El enfoque basado en la contracción de Wasserstein es más general que la ergodicidad geométrica o uniforme clásica. Permite recuperar estos casos clásicos como subconjuntos, pero también abarca escenarios donde las métricas tradicionales fallan.

4. Análisis del Régimen de "Pequeño $\beta$": Los autores identifican que las tasas de convergencia se deterioran cuando la adaptación es muy frecuente ($\beta < 1$). Sin embargo, demuestran que bajo condiciones adicionales (como una condición de Lipschitz uniforme y "adaptación que se desvanece" o waning adaptation), es posible recuperar las tasas óptimas incluso para $\beta \in (0, 1)$.

4. Resultados Principales

Los teoremas principales (3.5, 3.6, 3.11 y 3.16) proporcionan las siguientes conclusiones:

• Caso $\beta \ge 1$ (Adaptación Rara):
  Si la función de interés es Lipschitz y acotada, y se cumple la contracción de Wasserstein con eccentricidad acotada, la tasa de convergencia es:
  $$r(n) = \sqrt{n} (\log n)^{1/2 + \epsilon}$$
  Esto implica que el error de la media muestral decae casi como $1/\sqrt{n}$, lo cual es óptimo y comparable a la Ley del Logaritmo Iterado para variables i.i.d.

• Caso $\beta \in (0, 1)$ (Adaptación Más Frecuente):
  Sin condiciones adicionales, la tasa se degrada a $n^{1/2 + \epsilon}$ con $\epsilon$ dependiente de $\beta$.

  • Mejora: Si se asume que los parámetros de adaptación cambian suavemente (condición Lipschitz) y la magnitud de los cambios decae suficientemente rápido (waning adaptation), se recupera la tasa óptima $r(n) = \sqrt{n}(\log n)^{1/2+\epsilon}$ incluso para $\beta < 1$.

• Aplicaciones Específicas:

  • Ergodicidad Uniforme Simultánea: Se aplica a algoritmos donde la distancia es la métrica trivial (distancia total de variación).
  • Ergodicidad Geométrica Simultánea: Se aplica a algoritmos con condiciones de deriva y minorización, utilizando métricas ponderadas por funciones de Lyapunov.
  • Ergodicidad de Harris Débil: Se extiende a kernels que satisfacen condiciones de contracción débiles (teorema de Harris débil), útiles en espacios de dimensión infinita.

5. Significado e Impacto

• Rigor Teórico: El trabajo cierra una brecha importante en la teoría de MCMC adaptativo, proporcionando límites de convergencia casi segura (path-wise) en lugar de solo convergencia en distribución o en media cuadrática.
• Eficiencia Computacional: Confirma teóricamente que los algoritmos AIR pueden ser tan eficientes como los adaptativos completos, pero con la ventaja de que la adaptación menos frecuente reduce la carga computacional y simplifica el análisis de convergencia.
• Flexibilidad: Al basarse en contracciones de Wasserstein en lugar de métricas de variación total estrictas, el marco es aplicable a una gama más amplia de problemas, incluyendo aquellos con espacios de estado no acotados o distribuciones multimodales complejas.
• Práctica: Los resultados ofrecen a los practicantes garantías sobre la velocidad de convergencia de sus estimaciones, incluso cuando solo se ejecuta una única cadena (comportamiento de trayectoria), lo cual es crucial en aplicaciones donde no se pueden realizar múltiples réplicas.

En resumen, el artículo demuestra que los esquemas AIR, combinados con condiciones de contracción de Wasserstein, ofrecen un marco robusto y teóricamente sólido para el MCMC adaptativo, logrando tasas de convergencia casi óptimas sin depender de supuestos técnicos restrictivos comunes en la literatura anterior.