MCMC for frequentists?

[gusl]

MCMC is a class of methods, typically used by "full" Bayesians for sampling from the posterior probability. Some Bayesians (the "non-full" ones) may be happy with Maximum a Posteriori (MAP) estimate as a point estimate. The latter are faced with "merely" an optimization problem, and have no use for MCMC¹.

Running an MCMC method consists of doing a random walk according to a Markov Chain whose state-space is the parameter space. Steps are suggested by a "proposal distribution". After some "burn-in" time, we wave our hands and declare that the random walk has "mixed" (i.e. the walk's randomness has erased essentially all the information we had about our initial state), implying that we can consider our visited states as unbiased samples from the posterior (I wonder if formally-minded people analytically bound the mixing rate as a way to justify this assertion).

MCMC methods are based on ratios of probabilities, and are useful because they cancel out the intractable normalization term in energy-based models (such as Undirected Graphical Models).... but why should they only be used by Bayesians?

Frequentists are typically interested in finding the maximum likelihood estimate... but I see no reason why they should focus strictly on getting a point estimate. Shouldn't they be interested in places where the likelihood function is high (level sets)?

Tangentially, Monte Carlo methods were invented by physicists, who in this setting are typically interested in simulating things like the spin correlation as it decays with distance. Nothing Bayesian about that.

Here's a causal diagram showing the connection between Monte Carlo methods and Bayesianism:

Bayesian --> hard integrals --> Monte Carlo methods

(Thanks to Cosma Shalizi for the interesting discussion; The errors, if any, are all mine)

---

^{1 - they could cool all the way to 0 Kelvin, but that's already called "Simulated Annealing".}

Comments

[htowsner.livejournal.com]

I don't know that much about statistics, but I'd be quite curious about whether those using the MCMC method actually do have formal methods to confirm that the random walk has mixed sufficiently.

[gustavolacerda.livejournal.com]

I wasn't referring to "formal methods" (in the sense of using a formal proof-language like Coq), but rather the everyday informal rigour used by mathematicians.

If you're interested in formal methods in machine learning, the closest thing I can think of is AutoBayes (I hear it's closer to Mathematica than to Coq).

[htowsner.livejournal.com]

I understood that. I meant whether they had mathematical arguments to actually demonstrate that the original data had been randomized out in some rigorous way.

[gustavolacerda.livejournal.com]

Cosma sent me these links as potentially relevant:

http://dx.doi.org/10.1109/MCSE.2006.30
http://www.ams.org/bookstore-getitem/item=mbk-58