<p><p>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.</p></p>
Working Paper details
- DOI
- 10.1920/wp.cem.2007.1207
- Publisher
- IFS
Suggested citation
Belloni, A and Chernozhukov, V. (2007). On the computational complexity of MCMC-based estimators in large samples. London: IFS. Available at: https://ifs.org.uk/publications/computational-complexity-mcmc-based-estimators-large-samples (accessed: 16 May 2024).
Related documents
More from IFS
Understand this issue
Gender norms, violence and adolescent girls’ trajectories: Evidence from India
24 October 2022
Council funding is a numbers game in which everybody is losing
13 May 2024
Empty defence spending promises are a shot in the dark
29 April 2024
Policy analysis
ABC of SV: Limited Information Likelihood Inference in Stochastic Volatility Jump-Diffusion Models
We develop novel methods for estimation and filtering of continuous-time models with stochastic volatility and jumps using so-called Approximate Bayesian Compu- tation which build likelihoods based on limited information.
12 August 2014
Assessing the economic benefits of education: reconciling microeconomic and macroeconomic approaches
This CAYT report discusses the strengths and limitations of several approaches to assessing the effect of education on productivity.
14 March 2013
Misreported schooling, multiple measures and returns to educational qualifications
We provide a number of contributions of policy, practical and methodological interest to the study of the returns to educational qualifications in the presence of misreporting.
1 February 2012
Academic research
Understanding Society: minimising selection biases in data collection using mobile apps
2 February 2024
Robust analysis of short panels
8 January 2024
A coefficient of variation for ordered categorical data: Analyzing relative health inequality and ageing in the UK and relative human resource inequality and gender in Canada
21 December 2023