the surprisingly overlooked efficiency of SMC

At the Laplace demon’s seminar today (whose cool name I cannot tire of!), Nicolas Chopin gave a webinar with the above equally cool title. And the first slide debunking myths about SMC’s:

The second part of the talk is about a recent arXival Nicolas wrote with his student Hai-Dang DauI missed, about increasing the number of MCMC steps when moving the particles. Called waste-free SMC. Where only one fraction of the particles is updated, but this is enough to create a sort of independence from previous iterations of the SMC. (Hai-Dang Dau and Nicolas Chopin had to taylor their own convergence proof for this modification of the usual SMC. Producing a single-run assessment of the asymptotic variance.)

On the side, I heard about a very neat (if possibly toyish) example on estimating the number of Latin squares:

And the other item of information is that Nicolas’ and Omiros’ book, An Introduction to Sequential Monte Carlo, has now appeared! (Looking forward reading the parts I had not yet read.)

6 Responses to “the surprisingly overlooked efficiency of SMC”

  1. Hi,
    my talk was really not about HMC; the “tale of the crypt” I wanted to discuss here was “SMC suffers from the curse of dimensionality” (since the talk is about SMC).
    By “tale of the crypt”, I meant a vague statement that ppl keep repeating, which may or may not be correct, given the problem at hand.

    The exact thing I said about HMC can be found at 4.30′ on the video:

    but I don’t claim being an expert on HMC.

  2. Andrew Gelman Says:

    X:

    Wait—are you saying that HMC does not mix better than random walk Metropolis? It depends on the example, sure, but there are lots of examples where HMC mixes much better than random walk Metropolis. So I’m not quite sure what’s being claimed here?

    • Hey A., this is Nicolas’ first slide, itself taken from Omiros’, and I really liked… the title of that slide!
      You could get a look at his other slides or even their new book on SMC! (To be reviewed?)
      For my agnostic part, I do not have strong beliefs in one approach being superior to another in every circumstance. With Chopin’s and Dau’s “waste-free SMC” possibly implementing HMC steps on their moves to make the best of two worlds (if coming at a significant computational cost).

      • Andrew Gelman Says:

        X:

        I guess I’d like to see the example where HMC does not mix better than random walk Metropolis. I can believe that SMC can do all sorts of things, but that’s not random walk Metropolis, right? That’s SMC.

        I don’t think HMC is always best, but I thought that mixing better than random walk Metropolis was something it did. To put it another way, if we didn’t think that, we would not have put all this effort into implementing HMC in Stan. HMC is more complicated than random walk Metropolis, it can take lots of steps per iteration, . . . if it didn’t mix better, we’d have no reason to use it at all!

        So I can’t figure out what Nicolas is trying to say in this slide, unless by “random walk Metropolis” he really means SMC? But then why not just say SMC??

    • Hi Andrew,
      see my post above, which you might have missed. Again my talk was not about HMC at all.

      • Andrew Gelman Says:

        Hi, Nicolas. OK, I went to that point on the slide where you said it was just a “tale” that HMC/NUTS mixes better than Metropolis. But it’s not just a tale! We have lots of experience. You mention something about tuning, but Metropolis requires tuning too. So I just don’t buy that at all. Again, Metropolis has some advantages—it’s easier to program, and it doesn’t require gradient evaluations—so I can see that it can still have a role to play. But I think HMC mixing better is pretty much true.

        Also, I agree that HMC does not solve all problems and I’m not saying anything against SMC here. I’m just speaking specifically to that line on your slide.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.