4
$\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?

$\endgroup$
  • 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 May 25 '12 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 Jun 23 '12 at 15:35
3
$\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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Even though they do not in realistically complex problems. $\endgroup$ – Xi'an Dec 6 '14 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).

$\endgroup$
  • 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 Dec 6 '14 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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