Sequential quasi Monte Carlo

By Mathieu Gerber, Nicolas Chopin. 2015

82 citations recorded by the source corpus.

We derive and study sequential quasi Monte Carlo (SQMC), a class of algorithms obtained by introducing QMC point sets in particle filtering. SQMC is related to, and may be seen as an extension of, the array‐RQMC algorithm of L'Ecuyer and his colleagues. The complexity of SQMC is O{Nlog(N)} , where N is the number of simulations at each iteration, and its error rate is smaller than the Monte Carlo rate OP(N−1/2) . The only requirement to implement SQMC algorithms is the ability to write the simulation of particle xtn given xt−1n as a deterministic function of xt−1n and a fixed number of uniform variates. We show that SQMC is amenable to the same extensions as standard SMC, such as forward smoothing, backward smoothing and unbiased likelihood evaluation. In particular, SQMC may replace SMC within a particle Markov chain Monte Carlo algorithm. We establish several convergence results. We provide numerical evidence that SQMC may significantly outperform SMC in practical scenarios.

Subfields: Artificial Intelligence, Numerical Analysis, Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bharath K. Sriperumbudur
2. Kenji Fukumizu
3. Arthur Gretton
4. Bernhard Schölkopf
5. Motonobu Kanagawa
6. Simon Lacoste-Julien
7. Francis R. Bach
8. Chris J. Oates

In Numerical Analysis

1. Bharath K. Sriperumbudur
2. Kenji Fukumizu
3. Motonobu Kanagawa
4. Chris J. Oates
5. Mark A. Girolami
6. Simon Lacoste-Julien
7. Francis R. Bach
8. Fredrik Lindsten

In Statistics and Probability

1. Kenji Fukumizu
2. Bharath K. Sriperumbudur
3. Arthur Gretton
4. Chris J. Oates
5. Simon Lacoste-Julien
6. Bernhard Schölkopf
7. Motonobu Kanagawa
8. Francis R. Bach

In Probabilistic & Bayesian Methods

1. Bharath K. Sriperumbudur
2. Kenji Fukumizu
3. Motonobu Kanagawa
4. Francis R. Bach
5. Simon Lacoste-Julien
6. Bernhard Schölkopf
7. Arthur Gretton
8. Chris J. Oates

Citations in the corpus

• Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, methodology): “By replacing random sampling with a quasi-random number sequence, we obtain the already proposed sequential quasi-Monte Carlo scheme (Philomin et al., 2000; Ormoneit et al., 2001; Gerber and Chopin, 2014).”
• Convergence guarantees for kernel-based quadrature rules in misspecified settings (2016, background): “Because of this nice property, kernel quadratures have been studied extensively in recent years [7, 3, 5, 2, 17] and have started to find applications in machine learning and statistics [23, 14, 12, 6].”
• An iterative Bayesian filtering framework for fast and automated calibration of DEM models (2019, background): “In fact, the use of deterministic quasi-random numbers leads to the so-called sequential quasi-Monte Carlo (SQMC) filter [53], which is recently proved to have better accuracy and smaller error rate than the SMC filter which uses pseudo-random numbers [54].”
• Control Functionals for Quasi-Monte Carlo Integration (2015, background): “Challenging integration problems are common in contemporary statistics, for example when computing expectations, marginal probability densities or normalising constants, and QMC methods are therefore gaining importance in statistical applications [12, 17, 35].”