On the computational complexity of MCMC-based estimators in large samples
By: Alexandre Belloni [and] Victor Chernozhukov
Contributors: Chernozhukov, Victor; Massachusetts Institute of Technology. Dept. of Economics
Series: Working paper series / Massachusetts Institute of Technology, Dept. of Economics -- working paper 07-08; Working paper (Massachusetts Institute of Technology. Dept. of Economics) -- no. 07-08.
Publisher: Massachusetts Institute of Technology, Dept. of Economics
Published: 2007
Place of publication: Cambridge, MA
Language: eng
Number of pages: 37
Description: This paper studies the computational complexity of Bayesian and quasi-Bayesian estimation in large samples carried out using a basic Metropolis random walk. The framework covers cases where the underlying likelihood or extremum criterion function is possibly non-concave, discontinuous, and of increasing dimension. Using a central limit framework to provide structural restrictions for the problem, it is shown that the algorithm is computationally efficient. Specifically, it is shown that the running time of the algorithm in large samples is bounded in probability by a polynomial in the parameter dimension d, and in particular is of stochastic order d2 in the leading cases after the burn-in period. The reason is that, in large samples, a central limit theorem implies that the posterior or quasi-posterior approaches a normal density, which restricts the deviations from continuity and concavity in a specific manner, so that the computational complexity is polynomial. An application to exponential and curved exponential families of increasing dimension is given. Keywords: Computational Complexity, Metropolis, Large Samples, Sampling, Integration, Exponential family, Moment restrictions. JEL Classifications: C1, C11, C15, C6, C63.
Notes: "February 23, 2007."

Includes bibliographical references (p. 35-37).

Abstract in HTML and working paper for download in PDF available via World Wide Web at the Social Science Research Network.