On the role of interaction in sequential Monte Carlo algorithms

By Nick Whiteley, Anthony Lee, Kari Heine. 2013

70 citations recorded by the source corpus.

We introduce a general form of sequential Monte Carlo algorithm defined in terms of a parameterized resampling mechanism. We find that a suitably generalized notion of the Effective Sample Size (ESS), widely used to monitor algorithm degeneracy, appears naturally in a study of its convergence properties. We are then able to phrase sufficient conditions for time-uniform convergence in terms of algorithmic control of the ESS, in turn achievable by adaptively modulating the interaction between particles. This leads us to suggest novel algorithms which are, in senses to be made precise, provably stable and yet designed to avoid the degree of interaction which hinders parallelization of standard algorithms. As a byproduct, we prove time-uniform convergence of the popular adaptive resampling particle filter.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, 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

In Computational Mechanics

In Computer Networks and Communications

In Probabilistic & Bayesian Methods

Citations in the corpus

An Introduction to Probabilistic Programming (2018, methodology): “When addresses are ordered, we can implement a variety of resampling policies that generalize from SMC (Whiteley et al., 2016), such as policies that resample the subset of executions at an address α once all remaining executions have reached interrupts with addresses α′ > α.”
Venture: a higher-order probabilistic programming platform with programmable inference (2014, neutral): “Integrating sophisticated coupling strategies from the αSMC framework (Whiteley et al., 2013) into the inference language could also prove fruitful.”
Rethinking the Effective Sample Size (2018, result): “We could also non-linearly transform the unnormalised weights before normalising them as in other studies (Ionides, 2008; Koblents & Míguez, 2013; Vehtari & Gelman, 2015) (refer to a review in Martino et al., 2018).”
Bayesian State-Space Modelling on High-Performance Hardware Using LibBi (2013, unknown): “The development of asynchronous resampling methods to alleviate this bottleneck is still an active area of research (Murray 2011; Del Moral, Jacob, Lee, Murray, and Peters 2013; Whiteley, Lee, and Heine 2013; Murray, Lee, and Jacob 2014; Lee and Whiteley.”
A Compilation Target for Probabilistic Programming Languages (2014, unknown): “SMC is run indefinitely by simply repeatedly drawing independent sets of particles; in contrast to the PMCMC algorithms, this is known to be a biased estimator even as the number of iterations goes to infinity (Whiteley et al., 2013), and is not recommended as a general-purpose approach.”
The sample size required in importance sampling (2015, background): “ substantial body of work on the ecacy of the eective sample size as a diagnostic tool, possibly beginning with Liu and Chen [41] and Doucet, de Freitas and Gordon [23]. See Whiteley, Lee and Heine [58] for some latest results. Huggins and Roy [31] established similar properties for the 1-ESS. It wo”
Asynchronous Anytime Sequential Monte Carlo (2014, methodology): “The naı̈ve strategy of running SMC again and merging the resulting sets of particles is suboptimal due to bias (see [12] for explanation).”