Optimal scaling of MCMC algorithms: exploiting the symmetry of the Metropolis-Hastings formula
2026-07-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors present a straightforward method to understand how Metropolis-Hastings sampling algorithms behave as the number of dimensions increases. Their approach uses the symmetry in the Metropolis-Hastings formula and includes known results for algorithms like Random Walk Metropolis and MALA as special cases. They also introduce new optimal scaling rules for various proposal methods, including those based on differential equations. Their work covers target distributions formed by products of multiple factors, even when these factors scale differently. Notably, they show how to design proposals where the variance decreases more slowly with dimension compared to existing methods.
Metropolis-HastingsMarkov Chain Monte Carlo (MCMC)Random Walk MetropolisMALA (Metropolis Adjusted Langevin Algorithm)scaling propertieshigh-dimensional samplingproposal distributionsdifferential equation integratorsoptimal scaling
Authors
P. Dobson, J. M. Sanz-Serna, K. C. Zygalakis
Abstract
We present a simple, yet general approach to study the scaling properties as the dimensionality of Metropolised MCMC sampling algorithms increases. The study relies ultimately on the symmetry of the Metropolis-Hastings formula. Our findings contain, as particular cases, many known results for the Random Walk Metropolis, MALA and other algorithms. In addition, they provide, in an easy way, new optimal scaling results for a variety of proposal mechanisms, including implicit proposals and proposals generated with the help of differential equation integrators. The analysis applies to targets that are products of a given, not necessarily univariate distribution, and also to cases where the different terms in the product are scaled differently. We show how to construct gradient-based MALA-like proposals where the variance of the proposal as the dimension $d$ increases may be taken as $O(1/d^μ)$, with $μ>0$ arbitrarily small, to be compared with the values $μ= 1$ for Random Walk Metropolis and $μ=1/3$ for MALA.