On the computational complexity of MCMC-based estimators in large samples - Alexandre Belloni; Victor Chernozhukov (Centre for Microdata Methods and Practice (cemmap), 2007)
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.
Keywords: 330; Monte Carlo; Computational Complexity; Curved Exponential; Markovscher Prozess; Monte-Carlo-Methode; Mathematik