Local and Global Contraction Principles for MCMC Mixing

Technical Summary: Local and Global Contraction Principles for MCMC Mixing

Problem Statement
The paper addresses the quantitative analysis of mixing times for Markov Chain Monte Carlo (MCMC) algorithms. Specifically, it seeks to establish rigorous bounds on how quickly the distribution of a Markov chain converges to its stationary distribution (or a controlled approximation thereof). The authors focus on two distinct algorithmic settings where standard convergence analyses face limitations:

1. Projected Langevin Monte Carlo (P-LMC): Algorithms operating on compact convex domains with potentially non-convex smooth potentials.
2. Independent Metropolis–Hastings (IMH): Algorithms where the importance weight $w = d\pi/dq$ (ratio of target to proposal) may be unbounded, rendering global contraction arguments trivial.

The central challenge is to provide convergence guarantees that are explicit, applicable to a broad class of divergences (beyond Total Variation), and robust to non-convexity and heavy-tailed importance weights.

Methodology
The authors develop a framework based on Strong Data-Processing Inequalities (SDPI) applied to the $E_\gamma$-divergence (also known as the hockey-stick divergence) for $\gamma \ge 1$. The $E_\gamma$-divergence is defined as $E_\gamma(\mu\|\nu) = \sup_{A} \{\mu(A) - \gamma\nu(A)\}$.

The core theoretical insight is that $E_\gamma$-divergence serves as a "master" divergence. Through an integral representation (Equation 2 in the paper), controlling the full profile of $E_\gamma(\mu\|\nu)$ and $E_\gamma(\nu\|\mu)$ allows for the derivation of convergence bounds for a wide class of $f$-divergences (including KL, $\chi^2$, and Rényi divergences) and Rényi divergences.

The paper employs two distinct contraction strategies tailored to the geometry of the specific algorithms:

1. Global Contraction: For P-LMC, the authors decompose the transition kernel into a drift step, a Gaussian smoothing step, and a projection. They leverage the fact that Gaussian smoothing on a compact set induces a strict global contraction in $E_\gamma$-divergence.
2. Local Contraction: For IMH with unbounded weights, global contraction fails because the chain can reject proposals with probability near 1. The authors introduce a local contraction coefficient defined on a "core" set $C_R = \{w \le R\}$. They prove that this local coefficient controls the pointwise rejection probability on the core, while the error outside the core is governed by the tail profile $H_R = \pi(w > R)$.

Key Contributions and Results

1. Global SDPI for Projected Langevin Monte Carlo (P-LMC)

• Non-Convexity Handling: The authors prove that for smooth potentials on a compact convex set, P-LMC exhibits exponential convergence in $E_\gamma$-divergence for all $\gamma \ge 1$. Crucially, this result does not require the potential to be convex.
• Explicit Coefficients: The contraction coefficient is derived explicitly based on the diameter of the set after the drift step but before Gaussian smoothing. The rate depends on the ratio of this diameter to the noise scale $\sqrt{\eta}$.
• Arbitrary Batching: The framework accommodates arbitrary random-batch sampling schemes (e.g., Poisson sampling, sampling without replacement). The convergence rate is expressed as an average of batch-specific contraction coefficients, offering sharper bounds than worst-case smoothness assumptions when batch smoothness varies.
• Divergence Transfer: By controlling both forward and reverse $E_\gamma$ profiles, the authors derive explicit convergence bounds for KL, $\chi^2$, and Rényi divergences.

2. Local SDPI for Independent Metropolis–Hastings (IMH)

• Local Coefficient Definition: For the core $C_R = \{w \le R\}$, the authors define a local hockey-stick contraction coefficient $\rho_\alpha(R)$. They prove that under a non-atomic proposal, this coefficient directly upper-bounds the rejection probability $r(x)$ for any $x \in C_R$.
• Tail-Adaptive Bounds: The convergence bound is formulated in terms of the tail profile $H_R = \pi(w > R)$ and the local contraction rate. The bound takes the form:
  $$E_\gamma(\mu_k\|\pi) \lesssim (L+1) \left[ e^{-k H_R/R} + H_R \right]$$
  where $L$ is the warm-start constant.
• Heavy-Tailed Regimes: Unlike previous works that rely on finite moment assumptions ($E_q[w^p] < \infty$), this formulation remains effective even when no finite moment of order $p > 1$ exists. The authors demonstrate this with an example where $E_q[w^p] = \infty$ for all $p > 1$, yet their tail-profile bound yields an explicit (albeit slow) convergence rate.
• Recovery of Existing Rates: Under warm-start assumptions and finite moment conditions, the derived bounds recover the sharp polynomial rates established in prior work (e.g., [DJKW24]).

Significance and Claims
The paper claims to provide a unified structural perspective on MCMC mixing through the lens of $E_\gamma$-divergence and contraction principles.

• For P-LMC: It offers a "clean explanation" for why global contraction works on compact domains: the Gaussian smoothing step contracts the hockey-stick profile once the pre-noise image has a bounded diameter. This allows for convergence guarantees on non-convex potentials where previous sharp mixing-time analyses (often restricted to convex settings) failed.
• For IMH: It shifts the analysis from global uniform ergodicity (which fails for unbounded weights) to a local contraction framework. This approach decouples the mixing behavior on the high-probability core from the tail behavior, providing a more flexible and adaptive tool for analyzing algorithms with heavy-tailed importance weights.
• Methodological Advantage: The use of $E_\gamma$-divergence allows the authors to prove a single "full profile" bound that implies convergence for a broad class of $f$-divergences, rather than proving separate results for TV, KL, or $\chi^2$ distances.

The authors maintain modesty regarding optimality, noting that while their one-step contraction coefficients are tight for specific non-convex potentials, the multi-step bounds might be improved by analyzing nonlinear SDPI profiles that track the divergence level, rather than applying a single worst-case coefficient linearly. They also identify extending this viewpoint to nonlinear contraction profiles for more complex kernels (like MALA) as a direction for future work.