Archive for quasi-Monte Carlo methods

population quasi-Monte Carlo

Posted in Books, Statistics with tags , , , , , , , , , , , , on January 28, 2021 by xi'an

“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

Posted in Mountains, pictures, Statistics, Travel, University life with tags , , , , , , , , , , , on October 21, 2020 by xi'an

MCqMC 2020 live and free and online

Posted in pictures, R, Statistics, Travel, University life with tags , , , , , , , , , , , , , on July 27, 2020 by xi'an

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

Posted in Statistics with tags , , , , on April 29, 2020 by xi'an

“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 IF2

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 2m-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.

MCqMC2020 key dates

Posted in pictures, Statistics, Travel, University life with tags , , , , , , , , , on January 23, 2020 by xi'an

A reminder of the key dates for the incoming MCqMC2020 conference this summer in Oxford:

Feb 28, Special sessions/minisymposia submission
Mar 13, Contributed abstracts submission
Mar 27, Acceptance notification
Mar 27, Registration starts
May 8, End of early bird registration
June 12, Speaker registration deadline
Aug 9-14 Conference

and of the list of plenary speakers

Yves Atchadé (Boston University)
Jing Dong (Columbia University)
Pierre L’Ecuyer (Université de Montreal)
Mark Jerrum (Queen Mary University London)
Gerhard Larcher (JKU Linz)
Thomas Muller (NVIDIA)
David Pfau (Google DeepMind)
Claudia Schillings (University of Mannheim)
Mario Ullrich (JKU Linz)