Abstract
This is a collection of three written discussions of the paper "sequential quasi-Monte Carlo sampling" by M. Gerber and N. Chopin, following the presentation given before the Royal Statistical Society in London on December 10th, 2014.
Introduction
Standard Sequential Monte Carlo (SMC) methods, often called "particle filters," are the workhorses of Bayesian inference for dynamic systems. However, they rely on standard Monte Carlo sampling, which has a relatively slow error convergence rate of $O(N^{-1/2})$.
Quasi-Monte Carlo (QMC) methods offer a theoretical upgrade, promising error rates closer to $O(N^{-1})$. The challenge addressed in this collection of expert discussions is how to successfully port QMC into sequential settings. Unlike static integration, sequential models require resampling and moving "particles" through time, which traditionally breaks the deterministic structure that QMC relies on. The discussants evaluate whether the "SQMC" framework proposed by Gerber and Chopin holds up when applied to complex, real-world statistical problems.
Methodological Adaptations
The discussions highlight several novel methodological adaptations of SQMC:
- Deterministic Transforms for Discrete States: Arbel and Prünster propose a way to apply SQMC to Bayesian nonparametrics (like Dirichlet Process mixtures). They define a deterministic transform $\Gamma_t$ for discrete probability mass functions, allowing cluster allocations to be "sampled" using low-discrepancy sequences.
- Likelihood-Free SQMC (ABC): Robin Ryder introduces a population-based Approximate Bayesian Computation (ABC) sampler that uses Randomized Quasi-Monte Carlo (RQMC) sequences. This allows the algorithm to "know in advance" how many uniform variables are needed, improving efficiency in models where the likelihood is intractable.
- Hilbert Curve Mapping: Christian Robert discusses the use of Hilbert curves to map multi-dimensional particles to a one-dimensional line. This allows for a sorted resampling step that preserves the "low-discrepancy" property of the sequences across time steps.
Key Insights and Challenges
The Deterministic Transform Bottleneck
Christian Robert points out a major hurdle: QMC requires every step of a simulation to be expressed as a deterministic function of a fixed number of uniforms ($x = \Gamma(u)$). If a model has unknown parameters ($\theta$) or lacks an easy inverse CDF, the computational cost of this transform can outweigh the variance gains. Unless SQMC can move away from requiring specific deterministic representations, it may remain a niche activity.
Variance Reduction vs. Computational Cost
In the ABC toy example (a hidden Markov chain with Gaussian noise), the QMC version outperformed the standard sampler with a variance 30 times smaller for the same number of particles. However, this gain comes at a price.
Key Results and Scaling
The discussants reaffirm that SQMC can achieve error rates of $O(N^{-1} \log(N)^{d-1})$, which is asymptotically much faster than the $O(N^{-1/2})$ of standard Monte Carlo. However, practical implementation reveals a significant "computational explosion."
As illustrated in Figure 1, while standard ABC computation time increases linearly with the number of particles, the time for QMC-ABC grows non-linearly. This suggests that current software implementations (like the randtoolbox R package) for generating low-discrepancy points may have significant scaling overhead that could limit the method's utility for very large particle systems.
Limitations and Future Work
- High-Dimensional Scaling: The cost of using Hilbert curves grows quickly with dimension, which may limit SQMC to lower-dimensional state spaces.
- Implementation Efficiency: Future work is needed to optimize the generation of QMC sequences to address the non-linear time increase observed in experiments.
- Adaptive Thresholds: Ryder suggests that SQMC could be used to improve ABC estimators where the acceptance threshold is chosen as a quantile of a fixed number of attempts, a common practice that hasn't been fully explored with QMC.
Summary updated