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: 29 May 2007
Type: cemmap Working Paper, CWP12/07
DOI: 10.1920/wp.cem.2007.1207

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.

Download full version
Now published:
Alexandre Belloni and Victor Chernozhukov August 2009, On the computational complexity of MCMC-based estimators in large samples, Journal Article

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