5 ms·

I did a PhD on Monte Carlo methods, and I remember really enjoying how elegant the HMC is. But seeing this here I feel I should comment, in the event that anyon

by nvrmnd 4y ago

I did a PhD on Monte Carlo methods, and I remember really enjoying how elegant the HMC is. But seeing this here I feel I should comment, in the event that anyone happens to read this and thinks it would be a useful algorithm to implement. Words to heed: "Monte Carlo is an extremely bad method; it should only be used when all alternative methods are worse." -- Alan Sokal The reality of the situation is that you would only bother understanding and implementing such a complex algorithm if you had a rather difficult distribution to sample. Unfortunately, that means that you are very unlikely to know whether the answers you are getting are at all correct. You may have a bug in your code (highly likely), or the method's hyper parameters may be poorly tuned (likelier still), or the MCMC chain is not mixing rapidly leading to undetectable approximation error (almost certainly). Almost always I would recommend attempting to simplify whatever model you are approximating and to use a method where approximation quality can be assured, rather than attempting to approximate complex (high dimensional) distributions with a more efficient algorithm like HMC. Of course, sometimes you must approximate such models, and for this you should be glad the method exists, and good luck to you.

ailun 4y ago
Why wouldn’t you just use Stan or Pymc or one of the other dozen existing implementations with something like HMC? They use it as the default sampling algorithm.
- nvrmnd 4y ago
  Yes by all means, though I do hope anyone who is using this default algorithm is familiar with the other pitfalls I mention.
  - ckrapu 4y ago
    I love reading about mcmc. Would you mind linking your thesis?
  - ailun 4y ago
    To be clear, I don't disagree with you about MCMC. But wouldn't your first two pitfalls wouldn't be taken care of as much as possible by using a widely used library's implementation? All the libraries I'm aware of tune the HMC hyperparameters automatically - should I be more worried that there's something invisibly going wrong there? And your third pitfall applies to MCMC in general, not HMC in particular.
    - versteegen 4y ago
      > should I be more worried that there's something invisibly going wrong there? I have no experience with those tuners, but, absolutely. There's no way that some heuristics can generalise to every possible distribution you feed in. But if the distribution is "sufficiently" nice (which is your responsibility to ensure) then presumably they will work.
      - ailun 4y ago
        That's why I said "more worried," though. Of course you can't be sure that they are doing a perfect job for every situation. But I don't think I'm going to do a better job manually than those heuristics - that's why they mostly aren't exposed to the user in the usual workflows, because people who spend their lives researching best practices for these algorithms don't think it's a good idea most of the time. If those heuristics aren't working, you're better off reparameterizing your model rather than messing with them. Hence why I don't think they are worth worrying about too much.
    - nvrmnd 4y ago
      > should I be more worried that there's something invisibly going wrong there? I think what anyone should be cautious about is thinking that these more sophisticated methods can allow MCMC methods to significantly scale up to larger problems. But they are probably 2-10x at best, if it's well suited to your distribution (however you characterize that). Often it's not enough to keep up with the dimensionality of the models people want to use. I remember struggling to get this to work on a Bayesian neural network that was maybe 100 parameters, tiny by todays' standards. As for approximating hyper-parameters, again if it's an easy problem, sure, probably something will work. But I do have to say I find this really fascinating when you start to get into these harder problems with MCMC algorithms. The first thing that comes up is how do you know that a sampler is drawing samples from the correct distribution? how exactly do you quantify that? Usually each sampler takes the same amount of time to produce a sample, so what you're really comparing is which one is giving "better" samples. But.. they are all supposed to be drawing from the same distribution, so how can one sample be better than another. If they are not drawing from the same distribution, then how can you possibly know which one is the right one! So I'm simplifying the problem here, and not to disparage any of the fine work on autocorrelation and mixing rates and all that, but you have to admire just how impossible this is generally.
versteegen 4y ago
I also did a PhD on MCMC (for sampling images), and agree fully with everything you said. I'll just add that I never felt I could trust HMC at all (I hardly used it) because it was too abstract, I couldn't form much intuition about why it mightn't be mixing. On the other hand I could easily understand the deficiencies of Gibbs sampling (in my case, changing one pixel at a time) and work around them (somewhat). I came away thinking that a 'feed-forward' approximation with a fixed amount of computation (e.g. a probabilistic neural net) would have been a much superior method to MCMC.
- boulos 4y ago
  > superior method to MCMC Superior in what ways? I could imagine simplicity for many problems. Roughly "here, replace your complex simulation with this magic function approximator". But for problems where you're calculating a physical quantity with a true answer, I don't see NNs being "much superior".
  - versteegen 4y ago
    In my case I could decide how to model the thing I was trying to emulate (not simulate). Using models that are inherently difficult to sample from was not a great idea.
nextos 4y ago
> Unfortunately, that means that you are very unlikely to know whether the answers you are getting are at all correct. For large multilevel GLMs I have found Rhat and posterior predictive checks to be sufficient to diagnose HMC sampling issues. But, of course, these might not fall within the category of difficult distributions you mentioned.
cfcf14 4y ago
Amazing post, agree with everything you've said. I've always felt that the problems with advanced MCMC methods (HMC, RM-MC, etc) are even more painful when one looks at approximate bayesian methods - ADVI (variational approximation), SGLD (langevin dynamics), and so on. My grad research was on ABC-SMC methods, probably the last resort of all last resorts. There was a period a few years ago when it was all the rage to take arbitrary probabilistic programming models and just toss ADVI at it blindly with fancy tools like Pymc3 or stan. I feel like everybody eventually came to the conclusion that if the model was simple enough that you could guarantee that ADVI was actually correct, you didn't need it, and if it wasn't, you couldn't possibly verify you were approximating anything close to the true posterior. At least with HMC it would generally explode when dealing with pathological geometry (multimodality, non-identifiability, whatever), whereas lots of the approximate methods will 'converge' to completely incorrect answers. I know there's been some work on determining if things have gone off the rails (https://arxiv.org/pdf/1802.02538.pdf https://arxiv.org/pdf/1802.02538.pdf), but I couldn't ever find a place where it felt safe to use this stuff blindly.

by nvrmnd 4y ago

ailun 4y ago

Why wouldn’t you just use Stan or Pymc or one of the other dozen existing implementations with something like HMC? They use it as the default sampling algorithm.

nvrmnd 4y ago
Yes by all means, though I do hope anyone who is using this default algorithm is familiar with the other pitfalls I mention.
- ckrapu 4y ago
  I love reading about mcmc. Would you mind linking your thesis?
- ailun 4y ago
  To be clear, I don't disagree with you about MCMC. But wouldn't your first two pitfalls wouldn't be taken care of as much as possible by using a widely used library's implementation? All the libraries I'm aware of tune the HMC hyperparameters automatically - should I be more worried that there's something invisibly going wrong there? And your third pitfall applies to MCMC in general, not HMC in particular.
  - versteegen 4y ago
    > should I be more worried that there's something invisibly going wrong there? I have no experience with those tuners, but, absolutely. There's no way that some heuristics can generalise to every possible distribution you feed in. But if the distribution is "sufficiently" nice (which is your responsibility to ensure) then presumably they will work.
    - ailun 4y ago
      That's why I said "more worried," though. Of course you can't be sure that they are doing a perfect job for every situation. But I don't think I'm going to do a better job manually than those heuristics - that's why they mostly aren't exposed to the user in the usual workflows, because people who spend their lives researching best practices for these algorithms don't think it's a good idea most of the time. If those heuristics aren't working, you're better off reparameterizing your model rather than messing with them. Hence why I don't think they are worth worrying about too much.
  - nvrmnd 4y ago
    > should I be more worried that there's something invisibly going wrong there? I think what anyone should be cautious about is thinking that these more sophisticated methods can allow MCMC methods to significantly scale up to larger problems. But they are probably 2-10x at best, if it's well suited to your distribution (however you characterize that). Often it's not enough to keep up with the dimensionality of the models people want to use. I remember struggling to get this to work on a Bayesian neural network that was maybe 100 parameters, tiny by todays' standards. As for approximating hyper-parameters, again if it's an easy problem, sure, probably something will work. But I do have to say I find this really fascinating when you start to get into these harder problems with MCMC algorithms. The first thing that comes up is how do you know that a sampler is drawing samples from the correct distribution? how exactly do you quantify that? Usually each sampler takes the same amount of time to produce a sample, so what you're really comparing is which one is giving "better" samples. But.. they are all supposed to be drawing from the same distribution, so how can one sample be better than another. If they are not drawing from the same distribution, then how can you possibly know which one is the right one! So I'm simplifying the problem here, and not to disparage any of the fine work on autocorrelation and mixing rates and all that, but you have to admire just how impossible this is generally.

versteegen 4y ago

I also did a PhD on MCMC (for sampling images), and agree fully with everything you said. I'll just add that I never felt I could trust HMC at all (I hardly used it) because it was too abstract, I couldn't form much intuition about why it mightn't be mixing. On the other hand I could easily understand the deficiencies of Gibbs sampling (in my case, changing one pixel at a time) and work around them (somewhat). I came away thinking that a 'feed-forward' approximation with a fixed amount of computation (e.g. a probabilistic neural net) would have been a much superior method to MCMC.

boulos 4y ago
> superior method to MCMC Superior in what ways? I could imagine simplicity for many problems. Roughly "here, replace your complex simulation with this magic function approximator". But for problems where you're calculating a physical quantity with a true answer, I don't see NNs being "much superior".
- versteegen 4y ago
  In my case I could decide how to model the thing I was trying to emulate (not simulate). Using models that are inherently difficult to sample from was not a great idea.

nextos 4y ago

> Unfortunately, that means that you are very unlikely to know whether the answers you are getting are at all correct. For large multilevel GLMs I have found Rhat and posterior predictive checks to be sufficient to diagnose HMC sampling issues. But, of course, these might not fall within the category of difficult distributions you mentioned.

cfcf14 4y ago

Amazing post, agree with everything you've said. I've always felt that the problems with advanced MCMC methods (HMC, RM-MC, etc) are even more painful when one looks at approximate bayesian methods - ADVI (variational approximation), SGLD (langevin dynamics), and so on. My grad research was on ABC-SMC methods, probably the last resort of all last resorts. There was a period a few years ago when it was all the rage to take arbitrary probabilistic programming models and just toss ADVI at it blindly with fancy tools like Pymc3 or stan. I feel like everybody eventually came to the conclusion that if the model was simple enough that you could guarantee that ADVI was actually correct, you didn't need it, and if it wasn't, you couldn't possibly verify you were approximating anything close to the true posterior. At least with HMC it would generally explode when dealing with pathological geometry (multimodality, non-identifiability, whatever), whereas lots of the approximate methods will 'converge' to completely incorrect answers. I know there's been some work on determining if things have gone off the rails (https://arxiv.org/pdf/1802.02538.pdf https://arxiv.org/pdf/1802.02538.pdf), but I couldn't ever find a place where it felt safe to use this stuff blindly.