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

The authors study the implications of the statistical large sample theory for computational complexity of Bayesian and quasi-Bayesian estimation carried our using a canonical Metropolis random walk. Their analysis permits the parameter dimension of the problem to grow to infinity and allows the underlying log-likelihood or extremum criterion function to be discontinuous and/or nonconcave. The polynomial complexity is established by exploiting a CLT framework which provides the structural restriction on the problem, namely, that the posterior or quasi-posterior density approaches a normal density in large samples. The interest is focused on (general) Metropolis random walk. A second task of interest is computing a high dimensional integral of a bounded real valued function. The applications to exponential families, curved exponential families and Z-estimation of increasing dimension concludes the paper.