Local and Global Contraction Principles for MCMC Mixing

Technische Samenvatting: Lokale en Globale Contractieprincipes voor MCMC-mixing

Probleemstelling
Het artikel behandelt de kwantitatieve analyse van mengtijden (mixing times) voor Markov Chain Monte Carlo (MCMC) algoritmen. Specifiek streeft het naar het vaststellen van rigoureuze grenzen aan de snelheid waarmee de distributie van een Markov-keten convergeert naar zijn stationaire distributie (of een gecontroleerde benadering daarvan). De auteurs richten zich op twee afzonderlijke algoritmische settings waar standaard convergentieanalyses beperkingen ervaren:

1. Projected Langevin Monte Carlo (P-LMC): Algoritmen die opereren op compacte convexe domeinen met potentieel niet-convexe gladde potentialen.
2. Independent Metropolis–Hastings (IMH): Algoritmen waarbij de belangrijksgewichten $w = d\pi/dq$ (de ratio van de doelverdeling tot de voorstelverdeling) onbegrensd kunnen zijn, waardoor globale contractie-argumenten triviaal worden.

De centrale uitdaging is om convergentiegaranties te bieden die expliciet zijn, toepasbaar op een brede klasse van divergenties (voorbij de Totale Variatie), en robuust tegen niet-convexiteit en zware staarten in de belangrijksgewichten.

Methodologie
De auteurs ontwikkelen een raamwerk gebaseerd op Sterke Data-verwerkingsongelijkheid (SDPI) toegepast op de $E_\gamma$-divergentie (ook wel bekend als de hockey-stick divergentie) voor $\gamma \ge 1$. De $E_\gamma$-divergentie wordt gedefinieerd als $E_\gamma(\mu\|\nu) = \sup_{A} \{\mu(A) - \gamma\nu(A)\}$.

Het kerninzicht is dat $E_\gamma$-divergentie dient als een "master" divergentie. Door middel van een integraalrepresentatie (Vergelijking 2 in het artikel) maakt het controleren van het volledige profiel van $E_\gamma(\mu\|\nu)$ en $E_\gamma(\nu\|\mu)$ de afleiding van convergentiegrenzen mogelijk voor een brede klasse van $f$-divergenties (inclusief KL, $\chi^2$, en Rényi-divergenties) en Rényi-divergenties.

Het artikel gebruikt twee verschillende contractiestrategieën die zijn afgestemd op de geometrie van de specifieke algoritmen:

1. Globale Contractie: Voor P-LMC deconstrueren de auteurs de transitie-kernel in een drift-stap, een Gaussische smoothing-stap en een projectie. Ze maken gebruik van het feit dat Gaussische smoothing op een compacte verzameling een strikte globale contractie induceert in de $E_\gamma$-divergentie.
2. Lokale Contractie: Voor IMH met onbegrensde gewichten faalt globale contractie omdat de keten voorstellen met een waarschijnlijkheid nabij 1 kan verwerpen. De auteurs introduceren een lokale contractiecoëfficiënt gedefinieerd op een "kern"-verzameling $C_R = \{w \le R\}$. Ze bewijzen dat deze lokale coëfficiënt de puntgewijze verwerpingskans op de kern controleert, terwijl de fout buiten de kern wordt beheerst door het staartprofiel $H_R = \pi(w > R)$.

Belangrijkste Bijdragen en Resultaten

1. Globale SDPI voor Projected Langevin Monte Carlo (P-LMC)

• Omgang met Niet-Convexiteit: De auteurs bewijzen dat voor gladde potentialen op een compacte convexe verzameling, P-LMC exponentiële convergentie vertoont in $E_\gamma$-divergentie voor alle $\gamma \ge 1$. Cruciaal is dat dit resultaat geen convexe potentiaal vereist.
• Expliciete Coëfficiënten: De contractiecoëfficiënt wordt expliciet afgeleid op basis van de diameter van de verzameling na de drift-stap maar vóór de Gaussische smoothing. De snelheid hangt af van de ratio van deze diameter tot de ruisschaal $\sqrt{\eta}$.
• Willekeurige Batching: Het raamwerk faciliteert willekeurige random-batch sampling-schema's (bijv. Poisson-sampling, sampling zonder teruglegging). De convergentiesnelheid wordt uitgedrukt als een gemiddelde van batch-specifieke contractiecoëfficiënten, wat scherpere grenzen biedt dan worst-case gladheid-aannames wanneer de batch-gladheid varieert.
• Divergentie-overdracht: Door zowel de voorwaartse als de achterwaartse $E_\gamma$-profielen te controleren, leiden de auteurs expliciete convergentiegrenzen af voor KL-, $\chi^2$- en Rényi-divergenties.

2. Lokale SDPI voor Independent Metropolis–Hastings (IMH)

• Definitie van Lokale Coëfficiënt: Voor de kern $C_R = \{w \le R\}$ definiëren de auteurs een lokale hockey-stick contractiecoëfficiënt $\rho_\alpha(R)$. Ze bewijzen dat onder een niet-atomaire voorstelverdeling deze lokale coëfficiënt direct de verwerpingskans $r(x)$ voor elke $x \in C_R$ begrenst.
• Staart-adaptieve Grenzen: De convergentie-grens wordt geformuleerd in termen van het staartprofiel $H_R = \pi(w > R)$ en de lokale contractiesnelheid. De grens heeft de vorm:
  $$E_\gamma(\mu_k\|\pi) \lesssim (L+1) \left[ e^{-k H_R/R} + H_R \right]$$
  waarbij $L$ de warm-start constante is.
• Heavy-Tailed Regimes: In tegenstelling tot eerder werk dat steunt op eindige moment-aannames ($E_q[w^p] < \infty$), blijft deze formulering effectief, zelfs wanneer geen enkel eindig moment van orde $p > 1$ bestaat. De auteurs demonstreren dit met een voorbeeld waarbij $E_q[w^p] = \infty$ voor alle $p > 1$, maar hun staartprofiel-grens toch een expliciete (zij het trage) convergentiesnelheid oplevert.
• Herstel van Bestaande Snelheden: Onder warm-start aannames en eindige moment-condities herstellen de afgeleide grenzen de scherpe polynomiale snelheden die in eerder werk zijn vastgesteld (bijv. [DJKW24]).

Betekenis en Claims
Het artikel claimt een verenigd structureel perspectief te bieden op MCMC-mixing door de lens van $E_\gamma$-divergentie en contractieprincipes.

• Voor P-LMC: Het biedt een "heldere verklaring" voor waarom globale contractie werkt op compacte domeinen: de Gaussische smoothing-stap contracteert het hockey-stick profiel zodra de pre-noise afbeelding een begrensde diameter heeft. Dit maakt convergentiegaranties mogelijk voor niet-convexe potentialen waar eerdere scherpe mixing-tijd analyses (vaak beperkt tot convexe settings) faalden.
• Voor IMH: Het verschuift de analyse van globale uniforme ergodiciteit (die faalt bij onbegrensde gewichten) naar een lokale contractie framework. Deze aanpak ontkoppelt het menggedrag op de hoog-waarschijnlijkheid kern van het staartgedrag, wat een flexibeler en adaptiever instrument biedt voor het analyseren van algoritmen met heavy-tailed belangrijksgewichten.
• Methodologisch Voordeel: Het gebruik van $E_\gamma$-divergentie stelt de auteurs in staat om een enkele "volledige profiel" grens te bewijzen die convergentie voor een brede klasse van $f$-divergenties impliceert, in plaats van aparte resultaten te bewijzen voor TV, KL of $\chi^2$ afstanden.

De auteurs blijven bescheiden over optimaliteit en merken op dat hoewel hun één-stap contractiecoëfficiënten scherp zijn voor specifieke niet-convexe potentialen, de meer-stap grenzen verbeterd kunnen worden door niet-lineaire SDPI-profielen te analyseren die de divergentieniveaus volgen, in plaats van een enkele worst-case coëfficiënt lineair toe te passen. Ze identificeren ook het uitbreiden van dit standpunt naar niet-lineaire contractieprofielen voor complexere kernels (zoals MALA) als een richting voor toekomstig werk.