Concentration inequalities and UQ bounds for hypocoercive MCMC samplers

Jeremiah Birrell, Luc Rey-BelletQuarterly 2019 · arXiv

TL;DR

This paper provides theoretical guarantees for the performance of a class of "hypocoercive" Markov Chain Monte Carlo (MCMC) samplers. It introduces new concentration inequalities and uncertainty quantification (UQ) bounds, offering explicit confidence intervals for computed expectations and quantifying the bias introduced by using approximate models.

What Problem Does This Paper Address?

When using MCMC methods to estimate expected values of functions with respect to a target distribution (especially when the normalizing constant is unknown), we rely on finite-time averages of samples from a stochastic process. Evaluating the performance of these samplers is crucial. Traditional methods often focus on asymptotic properties like the asymptotic variance. This paper tackles the problem of providing non-asymptotic performance guarantees, which are more direct and useful for practical applications. Specifically, it addresses how well a finite-time average approximates the true expectation and how robust these approximations are to uncertainties in the model used for sampling. The focus is on a class of samplers called "hypocoercive" systems, which are non-reversible and don't satisfy standard "coercive" conditions, but still exhibit fast convergence to equilibrium. Examples include the Langevin equation, Hamiltonian Monte Carlo, and bouncy particle/zig-zag samplers.

Methods

The core of the paper lies in developing concentration inequalities for ergodic averages of hypocoercive MCMC samplers. This is achieved by:

  • Leveraging Hypocoercivity: The authors build upon recent advances in the theory of hypocoercivity, particularly the work of Dolbeault, Mouhot, and Schmeiser, which provides estimates for the convergence rate of these systems. This theory involves analyzing the generator of the Markov process in a modified inner product space.
  • Feynman-Kac Semigroups and Chernoff Bounds: They adapt techniques from earlier work on coercive systems (specifically, by Wu and Gao et al.) that utilize Feynman-Kac semigroups and Chernoff bounds. These tools allow for bounding probabilities of deviations from the mean.
  • Concentration Inequalities: By combining the hypocoercive estimates with the Feynman-Kac/Chernoff bound machinery, they derive Bernstein-type concentration inequalities. These inequalities provide explicit bounds on how likely it is for the finite-time average to deviate from the true expectation by a certain amount.
  • Uncertainty Quantification (UQ) Bounds: The paper extends these concentration inequalities to provide UQ bounds. This is done by considering a "baseline" hypocoercive model and an "alternative" (potentially approximate or unknown) process. Using relative entropy between the path-space distributions of these processes, they bound the bias introduced by using the baseline model.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on deriving general results for a class of stochastic processes.

Key Insights and Ideas

  • Generalizing Performance Guarantees: The most significant insight is the successful extension of non-asymptotic concentration inequalities and UQ bounds from coercive MCMC samplers to the broader class of hypocoercive samplers. This significantly expands the applicability of these performance guarantees.
  • Hypocoercivity as a Bridge: The paper demonstrates how the mathematical framework of hypocoercivity, particularly the use of modified inner products and associated Poincaré-type inequalities, can be effectively used to derive these probabilistic bounds.
  • Unified Approach: The authors present a unified approach that leverages existing techniques (Feynman-Kac, Chernoff bounds) and adapts them to the specific properties of hypocoercive systems, showing the power of this combination.
  • Practical Implications: The derived bounds offer concrete tools for practitioners:
  • Confidence Intervals: Explicit, non-asymptotic confidence intervals for estimated expectations, which are more informative than just asymptotic variance.
  • Model Robustness: Quantifying how sensitive the estimation results are to inaccuracies or approximations in the chosen MCMC model.

Key Results

  • Theorem 1.1 (Non-asymptotic Confidence Intervals): Provides explicit, non-asymptotic confidence intervals for the ergodic average of a function $f$ with respect to the invariant measure $\mu^*$. These intervals are valid for any finite time $T$ and confidence level $1-\delta$.
  • Theorem 1.2 (Uncertainty Quantification Bounds): Derives bounds on the bias of the finite-time ergodic average when comparing a baseline hypocoercive process to an alternative process. These bounds depend on the relative entropy between the path-space distributions and the hypocoercive properties of the baseline model.
  • Corollary 1: A direct application of the main concentration inequality, yielding explicit confidence intervals for the ergodic average.

Limitations and Future Work

  • Constant Dependence: While the bounds are explicit, the constants involved can be complex and depend on various parameters of the hypocoercive system (e.g., spectral gaps, Poincaré constants). The paper refers to other works for explicit computation of these constants.
  • Assumptions: The results rely on the hypocoercive estimate (1.4) and specific conditions on the modified inner product and the generator of the process. Verifying these conditions for specific samplers is a separate task.
  • Future Work: The paper suggests that the framework can be extended to other types of systems and potentially to discrete-time MCMC methods. The authors also point to the need for explicit computation of the constants for practical applications.

Summary updated

Abstract

In this work we provide performance guarantees for hypocoercive nonreversible Monte-Carlo Markov chain (MCMC) samplers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X Subscript t"> <mml:semantics> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">X_t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with invariant measure <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu Subscript asterisk"> <mml:semantics> <mml:msub> <mml:mi> μ </mml:mi> <mml:mo> ∗ </mml:mo> </mml:msub> <mml:annotation encoding="application/x-tex">\mu _*</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ; our results apply in particular to the Langevin equation, Hamiltonian Monte-Carlo, and the bouncy particle and zig-zag samplers. Specifically, we establish a concentration inequality of Bernstein type for ergodic averages <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartFraction 1 Over upper T EndFraction integral Subscript 0 Superscript upper T Baseline f left-parenthesis upper X Subscript t Baseline right-parenthesis d t"> <mml:semantics> <mml:mrow> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>T</mml:mi> </mml:mfrac> <mml:msubsup> <mml:mo> ∫ </mml:mo> <mml:mn>0</mml:mn> <mml:mi>T</mml:mi> </mml:msubsup> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mi>d</mml:mi> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\frac {1}{T} \int _0^T f(X_t)\, dt</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . As a consequence we provide two types of performance guarantees: (a) explicit nonasymptotic confidence intervals for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="integral f d mu Subscript asterisk"> <mml:semantics> <mml:mrow> <mml:mo> ∫ </mml:mo> <mml:mi>f</mml:mi> <mml:mi>d</mml:mi> <mml:msub> <mml:mi> μ </mml:mi> <mml:mo> ∗ </mml:mo> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">\int f d\mu _*</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when using a finite time ergodic average with given initial condition <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu"> <mml:semantics> <mml:mi> μ </mml:mi> <mml:annotation encoding="application/x-tex">\mu</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and (b) uncertainty quantification (UQ) bounds, expressed in terms of relative entropy rate, on the bias of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="integral f d mu Subscript asterisk"> <mml:semantics> <mml:mrow> <mml:mo> ∫ </mml:mo> <mml:mi>f</mml:mi> <mml:mi>d</mml:mi> <mml:msub> <mml:mi> μ </mml:mi> <mml:mo> ∗ </mml:mo> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">\int f d\mu _*</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when using an alternative or approximate processes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X overTilde Subscript t"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>X</mml:mi> <mml:mo> ~ </mml:mo> </mml:mover> </mml:mrow> <mml:mi>t</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\widetilde {X}_t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . (Results in (b) generalize results of the authors [ <italic>Uncertainty quantification for Markov processes via variational principles and functional inequalities</italic> , SIAM/ASA J. Uncertain. Quantif. 8 (2020), no. 2, 539–572] for coercive dynamics.) The concentration inequality is proved by combining the approach via Feynman-Kac semigroups first noted by Wu [ <italic>A deviation inequality for non-reversible Markov processes</italic> , Ann. Inst. H. Poincaré Probab. Statist. 36 (2000), no. 4, 435–445] with the hypocoercive estimates of Dolbeault, Mouhot, and Schmeiser [ <italic>Hypocoercivity for kinetic equations with linear relaxation terms</italic> , C. R. Math. Acad. Sci. Paris 347 (2009), no. 9–10, 511–516] and [ <italic>Hypocoercivity for linear kinetic equations conserving mass</italic> , Trans. Amer. Math. Soc. 367 (2015), no. 6, 3807–3828] developed for the Langevin equation and generalized to partially deterministic Markov processes by Andrieu, Durmus, Nüsken, and Roussel [ <italic>Hypocoercivity of piecewise deterministic Markov process-Monte Carlo</italic> , Ann. Appl. Probab. 31 (2021), no. 5, 2478–2517].
BibTeX
@inproceedings{birrell2019concentration,
  author = {Jeremiah Birrell and Luc Rey-Bellet},
  title = {{Concentration inequalities and UQ bounds for hypocoercive MCMC samplers}},
  booktitle = {Quarterly},
  year = {2019},
}
Figure