Introduction to Sequential Monte Carlo [book review]

[Warning: Due to many CoI, from Nicolas being a former PhD student of mine, to his being a current colleague at CREST, to Omiros being co-deputy-editor for Biometrika, this review will not be part of my CHANCE book reviews.]

My friends Nicolas Chopin and Omiros Papaspiliopoulos wrote in 2020 An Introduction to Sequential Monte Carlo (Springer) that took several years to achieve and which I find remarkably coherent in its unified presentation. Particles filters and more broadly sequential Monte Carlo have expended considerably in the last 25 years and I find it difficult to keep track of the main advances given the expansive and heterogeneous literature. The book is also quite careful in its mathematical treatment of the concepts and, while the Feynman-Kac formalism is somewhat scary, it provides a careful introduction to the sampling techniques relating to state-space models and to their asymptotic validation. As an introduction it does not go to the same depths as Pierre Del Moral’s 2004 book or our 2005 book (Cappé et al.). But it also proposes a unified treatment of the most recent developments, including SMC² and ABC-SMC. There is even a chapter on sequential quasi-Monte Carlo, naturally connected to Mathieu Gerber’s and Nicolas Chopin’s 2015 Read Paper. Another significant feature is the articulation of the practical part around a massive Python package called particles [what else?!]. While the book is intended as a textbook, and has been used as such at ENSAE and in other places, there are only a few exercises per chapter and they are not necessarily manageable (as Exercise 7.1, the unique exercise for the very short Chapter 7.) The style is highly pedagogical, take for instance Chapter 10 on the various particle filters, with a detailed and separate analysis of the input, algorithm, and output of each of these. Examples are only strategically used when comparing methods or illustrating convergence. While the MCMC chapter (Chapter 15) is surprisingly small, it is actually an introducing of the massive chapter on particle MCMC (and a teaser for an incoming Papaspiloulos, Roberts and Tweedie, a slow-cooking dish that has now been baking for quite a while!).

population quasi-Monte Carlo

“Population Monte Carlo (PMC) is an important class of Monte Carlo methods, which utilizes a population of proposals to generate weighted samples that approximate the target distribution”

A return of the prodigal son!, with this arXival by Huang, Joseph, and Mak, of a paper on population Monte Carlo using quasi-random sequences. The construct is based on an earlier notion of Joseph and Mak, support points, which are defined wrt a given target distribution F as minimising the variability of a sample from F away from these points. (I would have used instead my late friend Bernhard Flury’s principal points!) The proposal uses Owen-style scrambled Sobol points, followed by a deterministic mixture weighting à la PMC, followed by importance support resampling to find the next location parameters of the proposal mixture (which is why I included an unrelated mixture surface as my post picture!). This importance support resampling is obviously less variable than the more traditional ways of resampling but the cost moves from O(M) to O(M²).

“The main computational complexity of the algorithm is O(M²) from computing the pairwise distance of the M weighted samples”

The covariance parameters are updated as in our 2008 paper. This new proposal is interesting and reasonable, with apparent significant gains, albeit I would have liked to see a clearer discussion of the actual computing costs of PQMC.

QMC at CIRM

MCqMC 2020 live and free and online

The MCqMC 20202 conference that was supposed to take place in Oxford next 9-14 August has been turned into an on-line free conference since travelling remains a challenge for most of us. Tutorials and plenaries will be live with questions  on Zoom, with live-streaming and recorded copies on YouTube. They will probably be during 14:00-17:00 UK time (GMT+1),  15:00-18:00 CET (GMT+2), and 9:00-12:00 ET. (Which will prove a wee bit of a challenge for West Coast and most of Asia and Australasia researchers, which is why our One World IMS-Bernoulli conference we asked plenary speakers to duplicate their talks.) All other talks will be pre-recorded by contributors and uploaded to a website, with an online Q&A discussion section for each. As a reminder here are the tutorials and plenaries:

Invited plenary speakers:

Aguêmon Yves Atchadé (Boston University)
Jing Dong (Columbia University)
Pierre L’Écuyer (Université de Montréal)
Mark Jerrum (Queen Mary University London)
Peter Kritzer (RICAM Linz)
Thomas Muller (NVIDIA)
David Pfau (Google DeepMind)
Claudia Schillings (University of Mannheim)
Mario Ullrich (JKU Linz)

Tutorials:

Fred Hickernell (IIT) — Software for Quasi-Monte Carlo Methods
Aretha Teckentrup (Edinburgh) — Markov chain Monte Carlo methods

Markov chain quasi-Monte Carlo

“It is known that Tausworthe generators can be viewed as polynomial Korobov lattice point sets with a denominator polynomial p(x) and a numerator polynomial q(x) over IF₂“

A recently arXived paper by Shin Harase, “A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo”, discusses the use of [quasi-Monte Carlo] Tausworthe generators rather than iid uniform sampling. As shown by Owen and Tribble, it is indeed legit to replace a sequence of iid (pseudo-random) uniforms with its quasi-Monte Carlo (qMC) version if the sequence keeps a sufficient degree of uniformity. The current paper optimises the parameters of the Tausworthe generators in terms of the t-value of the generator, an indicator of the uniform occupancy of the qMC sequence.

For a range of values of m, if 2^m-1 is the period of the pseudo-random generator, the author obtains the optimal weights in the Tausworthe generator, which is a linear feedback shift register generator over {0,1}, ie shifting all the bits of the current uniform realisation by linear combination modulo 2. The comparison with other qMC and MC is provided on a Gibbs sampler for a bidimensional Gaussian target, which presents the advantage of requiring exactly one uniform per simulation and the disadvantage of … requiring exactly one uniform per simulation! Since this is harder to envision for simulation methods requiring a random number of uniforms.

Regarding the complexity of the approach, I do not see any gap between using these Tausworthe generators and something like the Mersenne generator. I just wonder at the choice of m, that is, whether or not it makes sense to pick any value lower than 2³² for the period.