6
$\begingroup$

There's a heuristic, which I find appealing, that says that for every stochastic algorithm, there should be at least one deterministic algorithm that performs better, provided the universe isn't adversarial. I first heard this principle articulated by Eliezer Yudkowsky here.

Markov Chain Monte Carlo algorithms, which are some of the post powerful and general algorithms for approximating probability distributions are, seem like a counterexample to this principle. Has there been much investigation into algorithms which take their inspiration from MCMC algorithms (I'm mostly thinking of Metropolis Hastings and Hamiltonian Monte Carlo), but which are totally deterministic? If not, why not?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Well, for your sentence "for every stochastic algorithm, there should be at least one deterministic algorithm that performs better", there is a counterpart written by David Mumford link. $\endgroup$
    – user10525
    Commented May 25, 2012 at 23:33
  • 1
    $\begingroup$ Do "better" in what sense? Achieve a goal with less computation? Less storage? Come closer to the goal (a better near-optimum, more accuracy, etc)? Provide more insight? Are these senses to be taken universally or perhaps just asymptotically or almost surely? $\endgroup$
    – whuber ♦
    Commented Jun 23, 2012 at 15:35

3 Answers 3

Reset to default
4
$\begingroup$

There is a great deal of work in the physics and chemistry communities using Hamiltonian dynamics, which can in many ways be seen as the deterministic equivalent to Markov chains. I don't know the literature well at all but Radford Neal's recent review of Hamiltonian MCMC discusses these ideas in some detail and provides a number of useful links.

Improve this answer
$\endgroup$
4
$\begingroup$

Also, there are quadrature methods (fully deterministic) and quasi-Monte Carlo methods which can outperform regular MCMC.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Even though they do not in realistically complex problems. $\endgroup$
    – Xi'an
    Commented Dec 6, 2014 at 19:39
0
$\begingroup$

As a deterministic alternative method for MCMC, I can mention INLA method which is introduced by Havard Rue and his colleagues at NTNU, Norway, for modeling a broad class of models, named Latent Gaussian Models. For more details see R-INLA webpage (http//www.r-inla.org).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ INLA is approximative in that it does not produce the exact posterior distribution but a Gaussian approximation instead. It may also contain simulations for the non-Gaussian part. $\endgroup$
    – Xi'an
    Commented Dec 6, 2014 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.