Poincaré inequalities for Markov chains: a meeting with Cheeger, Lyapunov and Metropolis

Christophe Andrieu, Anthony Lee, Sam Power, Andi Q. WangarXiv 2022 · DOI · arXiv

TL;DR

This paper provides a comprehensive functional-analytic framework for analyzing the convergence of discrete-time Markov chains, particularly those that converge slower than the standard "geometric" rate. By developing a theory of Weak Poincaré Inequalities (WPIs), the authors bridge the gap between classical drift-and-minorization techniques and modern spectral analysis, offering new tools to bound convergence rates and asymptotic variance in MCMC algorithms.

What Problem Does This Paper Address?

In the world of Markov Chain Monte Carlo (MCMC), we usually want our chains to be "geometrically ergodic"—meaning they converge to the target distribution at an exponential rate. When a chain is geometrically ergodic, it has a "spectral gap," a standard measure of efficiency.

However, many modern, complex algorithms (like those targeting heavy-tailed distributions or using pseudo-marginal methods) are subgeometric. They converge, but more slowly (e.g., polynomially). The classical toolkit for these chains—largely based on the Meyn-Tweedie drift and minorization approach—can be difficult to apply quantitatively. While the physics and math communities have a rich "functional-analytic" toolkit for continuous-time processes (like diffusions), a similar, cohesive framework for discrete-time Markov chains was missing. This paper fills that gap.

Methods

The authors center their approach on Weak Poincaré Inequalities (WPIs). Unlike a standard Poincaré inequality, which assumes a constant spectral gap, a WPI allows the "gap" to depend on the properties of the function being integrated (using what the authors call a "sieve functional").

Key methodological contributions include:

  • Unified Parameterization: They prove the equivalence of different ways to define WPIs, making the theory more flexible for practitioners.
  • The "Meeting": They show how WPIs connect three traditionally separate areas of Markov chain theory:
  • Cheeger Inequalities: Relating convergence to "conductance" (how easily the chain moves between sets).
  • Lyapunov Functions: Using drift conditions to establish local Poincaré inequalities that can be "glued" together to understand global behavior.
  • Metropolis-Hastings: Applying these tools specifically to analyze the most common class of MCMC algorithms.
  • RUPI Equivalence: They establish that the existence of a WPI is equivalent to a property called "resolvent-uniform-positivity-improving" (RUPI), providing a fundamental link between functional analysis and Markov chain stability.

Datasets

As a theoretical probability and statistics paper, no external empirical datasets were used. Instead, the authors evaluate their methods on canonical algorithmic models and target distributions:

  • Independent Metropolis-Hastings (IMH): Used to demonstrate spectral concentration.
  • Random Walk Metropolis (RWM): Tested on both Gaussian (light-tailed) and heavy-tailed target distributions.
  • Pseudo-marginal MCMC: A class of algorithms used when the target density cannot be evaluated exactly.

Key Insights and Ideas

  • Subgeometric is the New Geometric: The paper argues that WPIs are the "natural" language for subgeometric convergence, just as standard Poincaré inequalities are for geometric convergence.
  • Conductance Matters: The authors generalize the concept of conductance to a "weak conductance" profile, which allows them to bound convergence rates even when a traditional spectral gap doesn't exist.
  • Dimension Scaling: One of the "aha" moments is a direct proof of the $d^{-1}$ scaling of the spectral gap for the Random Walk Metropolis in high dimensions. While this scaling was widely "known" in the community, a direct functional-analytic proof for a broad class of light-tailed targets was a significant contribution.
  • Variance Bounding: They show that WPIs don't just tell you if a chain converges, but provide explicit upper bounds on the asymptotic variance of MCMC estimators, which is what practitioners actually care about for error bars.

Key Results

  • Theorem 7 (Convergence Rates): Provides an explicit recipe to turn a WPI into a quantitative convergence bound ($||P^n f||_2^2 \leq \gamma(n) \Phi(f)$).
  • High-Dimensional RWM: Established that for a class of log-concave, spherically symmetric targets, the spectral gap of the RWM scales as $O(d^{-1})$, providing a rigorous footing for optimal scaling results.
  • Heavy-Tailed Lower Bounds: The authors provide new lower bounds on convergence rates for RWM targeting heavy-tailed distributions, showing exactly how the "stickiness" in the tails prevents fast convergence.
  • Central Limit Theorems: They derive conditions under which subgeometric chains still satisfy a Central Limit Theorem (CLT), ensuring that MCMC averages eventually behave like normal distributions.

Limitations and Future Work

  • Spherical Symmetry: Some of the high-dimensional results assume the target distribution is spherically symmetric. The authors acknowledge this was for simplicity and suggest that these results likely extend to more general log-concave distributions.
  • Sieve Selection: While the paper provides a framework for "optimal" sieve functionals, choosing the right sieve for a brand-new, highly complex algorithm remains a non-trivial task for the user.
  • Discrete vs. Continuous: The authors note that discrete-time chains have "subtleties and challenges" not present in the continuous-time limit (like issues with periodicity or negative eigenvalues), suggesting that further refinement of these tools for non-reversible chains is a promising path forward.

Summary updated

Abstract

We develop a theory of weak Poincaré inequalities to characterize convergence rates of ergodic Markov chains. Motivated by the application of Markov chains in the context of algorithms, we develop a relevant set of tools which enable the practical study of convergence rates in the setting of Markov chain Monte Carlo methods, but also well beyond.
BibTeX
@misc{andrieu2022poincare,
  author = {Christophe Andrieu and Anthony Lee and Sam Power and Andi Q. Wang},
  title = {{Poincaré inequalities for Markov chains: a meeting with Cheeger, Lyapunov and Metropolis}},
  year = {2022},
  eprint = {2208.05239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.05239},
}

Loading related content...

Figure