Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the Computational Complexity of MCMC-based Estimators in Large
  Samples   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 the conditions required for the central limit theorem to hold, 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
non-concave, discontinuous, and with increasing parameter 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.
  Under minimal assumptions required for the central limit theorem to hold
under the increasing parameter dimension, we show that the Metropolis algorithm
is theoretically efficient even for the canonical Gaussian walk which is
studied in detail. Specifically, we show 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 $d^2$ in the leading
cases after the burn-in period. We then give applications to exponential
families, curved exponential families, and Z-estimation of increasing
dimension.

20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
19
The categories of this paper are: eess
27
The categories of this paper are: comp-gas
11
The categories of this paper are: hep-lat
8
The categories of this paper are: hep-ex
35
The categories of this paper are: mtrl-th
17
The categories of this paper are: q-fin
22
The categories of this paper are: chao-dyn
14
The categories of this paper are: math-ph
0
The categories of this paper are: hep-ph
12
The categories of this paper are: nucl-th
1
The categories of this paper are: cs
13
The categories of this paper are: quant-ph
26
The categories of this paper are: bayes-an
15
The categories of this paper are: nucl-ex