Title: Dual Spectral-Gap Certificates Enable Self-Certifying Transport MCMC

Abstract:

This paper introduces CerT-MCMC, a novel framework that integrates automatic and rigorous convergence verification into learned-transport Markov chain Monte Carlo (MCMC). In this approach, a normalizing flow transforms a Gaussian reference distribution into an approximation of the target posterior. This same flow functions dually as the proposal mechanism for independence Metropolis-Hastings sampling and as the foundation for deriving a computable spectral-gap bound.

We establish two distinct, complementary verification methods. The first, termed the covering certificate, utilizes finite-sample covering arguments to bound the oscillation of the weight ratio across the entire support of the proposal. When a conservative gradient bound is accessible, this yields full-support spectral-gap estimates. However, its correction term scales at a rate of $O(n^{-1/D})$, causing the bound to weaken rapidly and become vacuous as the dimensionality increases. We demonstrate that a lower bound of $\Omega(n^{-1/D})$ exists, confirming that this limitation is an inherent characteristic of pointwise Lipschitz certification.

The second method, the quantile-core certificate, narrows the focus to a high-probability residual core where oscillation is managed through one-dimensional empirical quantiles. This approach incurs a finite-sample probability slack of $O(n^{-1/2})$, which remains independent of the ambient dimension.

Empirical evaluations on synthetic targets (dimensions $D=2$ to $20$), structural-engineering posteriors ($D=6, 8$), real-world logistic regression on the Heart Disease dataset ($D=13$), and synthetic Bayesian logistic regression ($D=20$) show that the quantile-core certificate provides non-vacuous spectral-gap bounds in scenarios where the covering certificate fails. Furthermore, its spectral-gap proxy correlates closely with empirical effective sample sizes, deviating by no more than 7%. In a negative control experiment, the certificate successfully distinguished flow quality by a factor greater than 10, significantly outperforming acceptance rates, which differed by only 1.15x. To our knowledge, this dual-certificate framework represents the first instance of automatic, dimension-aware convergence verification for learned-transport MCMC, effectively differentiating between actual transport failures and limitations inherent to the proof techniques.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC