Hird, Max; Livingstone, Samuel; (2025) Quantifying the Effectiveness of Linear Preconditioning in Markov Chain Monte Carlo. Journal of Machine Learning Research (JMLR) , 26 pp. 1-51. (In press).

Preview

Text Livingstone_Preconditioning_for_MCMC-3.pdf Download (1MB) | Preview

Abstract

We study linear preconditioning in Markov chain Monte Carlo. We consider the class of well-conditioned distributions, for which several mixing time bounds depend on the condition number κ. First we show that well-conditioned distributions exist for which κ can be arbitrarily large and yet no linear preconditioner can reduce it. We then impose two sets of extra assumptions under which a linear preconditioner can significantly reduce κ. For the random walk Metropolis we further provide upper and lower bounds on the spectral gap with tight 1/κ dependence. This allows us to give conditions under which linear preconditioning can provably increase the gap. We then study popular preconditioners such as the covariance, its diagonal approximation, the Hessian at the mode, and the QR decomposition. We show conditions under which each of these reduce κ to near its minimum. We also show that the diagonal approach can in fact increase the condition number. This is of interest as diagonal preconditioning is the default choice in well-known software packages. We conclude with a numerical study comparing preconditioners in different models, and we show how proper preconditioning can greatly reduce compute time in Hamiltonian Monte Carlo.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item