centre for microdata methods and practice

ESRC centre

cemmap is an ESRC research centre

ESRC

Keep in touch

Subscribe to cemmap news

On the computational complexity of MCMC-based estimators in large samples

Authors: Alexandre Belloni and Victor Chernozhukov
Date: 01 August 2009
Type: Journal Article, Annals of Statistics, Vol. 37, No. 4, pp. 2011-2055

Abstract

In this paper we examine the implications of the statistical large sample theory for the computational complexity of Bayesian and quasi-Bayesian estimation carried out using Metropolis random walks. Our analysis is motivated by the Laplace-Bernstein-Von Mises central limit theorem, which states that in large samples the posterior or quasi-posterior approaches a normal density. Using this observation, we establish polynomial bounds on the computational complexity of general Metropolis random walks methods in large samples. Our analysis covers cases, where the underlying log-likelihood or extremum criterion function is possibly nonconcave, discontinuous, and of increasing dimension. However, the central limit theorem restricts the deviations from continuity and log-concavity of the log-likelihood or extremum criterion function in a very specific manner.

Previous version:
Alexandre Belloni and Victor Chernozhukov May 2007, On the computational complexity of MCMC-based estimators in large samples, cemmap Working Paper, CWP12/07

Publications feeds

Subscribe to cemmap working papers via RSS

Search cemmap

Search by title, topic or name.

Contact cemmap

Centre for Microdata Methods and Practice

How to find us

Tel: +44 (0)20 7291 4800

E-mail us