dorsal/arxiv
View SchemaVariational method for estimating the rate of convergence of Markov Chain Monte Carlo algorithms
| Authors | Fergal P. Casey, Joshua J. Waterfall, Ryan N. Gutenkunst, Christopher R. Myers, James P. Sethna |
|---|---|
| Categories | |
| ArXiv ID | physics/0609001 |
| URL | https://arxiv.org/abs/physics/0609001 |
| DOI | 10.1103/PhysRevE.78.046704 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
We demonstrate the use of a variational method to determine a quantitative lower bound on the rate of convergence of Markov Chain Monte Carlo (MCMC) algorithms as a function of the target density and proposal density. The bound relies on approximating the second largest eigenvalue in the spectrum of the MCMC operator using a variational principle and the approach is applicable to problems with continuous state spaces. We apply the method to one dimensional examples with Gaussian and quartic target densities, and we contrast the performance of the Random Walk Metropolis-Hastings (RWMH) algorithm with a ``smart'' variant that incorporates gradient information into the trial moves. We find that the variational method agrees quite closely with numerical simulations. We also see that the smart MCMC algorithm often fails to converge geometrically in the tails of the target density except in the simplest case we examine, and even then care must be taken to choose the appropriate scaling of the deterministic and random parts of the proposed moves. Again, this calls into question the utility of smart MCMC in more complex problems. Finally, we apply the same method to approximate the rate of convergence in multidimensional Gaussian problems with and without importance sampling. There we demonstrate the necessity of importance sampling for target densities which depend on variables with a wide range of scales.
{
"annotation_id": "bf8f6e33-0897-4f35-9472-1b656d4e4f14",
"date_created": "2026-03-02T18:01:11.154000Z",
"date_modified": "2026-03-02T18:01:11.154000Z",
"file_hash": "d68a2768c373eed8f9272ed4a779cdbf4612bbf3c7f57e59631de42340138cd2",
"private": false,
"record": {
"abstract": "We demonstrate the use of a variational method to determine a quantitative\nlower bound on the rate of convergence of Markov Chain Monte Carlo (MCMC)\nalgorithms as a function of the target density and proposal density. The bound\nrelies on approximating the second largest eigenvalue in the spectrum of the\nMCMC operator using a variational principle and the approach is applicable to\nproblems with continuous state spaces. We apply the method to one dimensional\nexamples with Gaussian and quartic target densities, and we contrast the\nperformance of the Random Walk Metropolis-Hastings (RWMH) algorithm with a\n``smart\u0027\u0027 variant that incorporates gradient information into the trial moves.\nWe find that the variational method agrees quite closely with numerical\nsimulations. We also see that the smart MCMC algorithm often fails to converge\ngeometrically in the tails of the target density except in the simplest case we\nexamine, and even then care must be taken to choose the appropriate scaling of\nthe deterministic and random parts of the proposed moves. Again, this calls\ninto question the utility of smart MCMC in more complex problems. Finally, we\napply the same method to approximate the rate of convergence in\nmultidimensional Gaussian problems with and without importance sampling. There\nwe demonstrate the necessity of importance sampling for target densities which\ndepend on variables with a wide range of scales.",
"arxiv_id": "physics/0609001",
"authors": [
"Fergal P. Casey",
"Joshua J. Waterfall",
"Ryan N. Gutenkunst",
"Christopher R. Myers",
"James P. Sethna"
],
"categories": [
"physics.data-an",
"physics.comp-ph"
],
"doi": "10.1103/PhysRevE.78.046704",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Variational method for estimating the rate of convergence of Markov Chain Monte Carlo algorithms",
"url": "https://arxiv.org/abs/physics/0609001"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5ea6a2c1-14d6-4822-96b1-ff57efb491e9",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}