Asynchronous Anytime Sequential Monte Carlo

By Brooks Paige, Frank D. Wood, Arnaud Doucet, Yee Whye Teh. 2014

48 citations recorded by the source corpus.

We introduce a new sequential Monte Carlo algorithm we call the particle cascade. The particle cascade is an asynchronous, anytime alternative to traditional sequential Monte Carlo algorithms that is amenable to parallel and distributed implementations. It uses no barrier synchronizations which leads to improved particle throughput and memory efficiency. It is an anytime algorithm in the sense that it can be run forever to emit an unbounded number of particles while keeping within a fixed memory budget. We prove that the particle cascade provides an unbiased marginal likelihood estimator which can be straightforwardly plugged into existing pseudo-marginal methods.

Subfields: Artificial Intelligence, 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

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

Design and Implementation of Probabilistic Programming Language Anglican (2016, methodology): “Asynchronous SMC (Particle Cascade) computes average particle weights at observe checkpoints [15].”
Inference Compilation and Universal Probabilistic Programming (2016, background): “…are many inference algorithms for universal probabilistic programming languages (Wingate et al., 2011; Ritchie et al., 2016a; Wood et al., 2014; Paige et al., 2014; Rainforth et al., 2016), we focus on algorithms in the importance sampling family in the context of which we will develop our…”
Practical probabilistic programming with monads (2015, methodology): “A final inference algorithm that we discuss here is the recently proposed Particle Cascade (PC) (Paige et al. 2014).”
Optimization Monte Carlo: Efficient and Embarrassingly Parallel Likelihood-Free Inference (2015, unknown): “Recently, a sequential Monte Carlo (SMC) algorithm called “the particle cascade” was introduced that emits streams of samples asynchronously with minimal memory management and communication [17].”
Inference Networks for Sequential Monte Carlo in Graphical Models (2016, background): “These are accompanied by complementary computational advances, including memory-efficient implementations (Jun and Bouchard-Côté, 2014), and highly-parallel variants (Murray et al., 2014; Paige et al., 2014).”
Probabilistic machine learning and artificial intelligence (2015, methodology): “Modern inference methods have made it possible to scale to millions of data points, making probabilistic methods computationally competitive with conventional methods 92–95 .”
Probabilistic Programming in Anglican (2015, methodology): “Among the available inference algorithms there are Particle Cascade [6], Lightweight Metropolis-Hastings [8], Iterative Conditional Sequential Monte-Carlo (Particle Gibbs) [9], and others.”