Asynchronous Anytime Sequential Monte Carlo
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.
In particle filtering, the resampling step is a synchronous operation: one needs all the particles before computing the normalised weights (since the denominator is the sum of all the weights), and then resample. The reviewed paper propose an asynchronous resampling mechanism, where the number of children of particle k depends only the weights of particles 1 to k. The proposed idea is quite straightforward, but still interesting and potentially very useful. What is a bit lacking in the current version is some motivation for an asynchronous implementation of particle filtering.  Having a different thread for each particles seems quite involved for many practical cases (recall that not every user of particle filtering works in CS), so providing a more substantial discussion (beyond citing two 2014 papers) would be tremendously helpful. Perhaps one step in this direction is to clarify a bit the discussion of Figure 3. Is it the case that "SMC" means a version of SMC where the set of particles are distributed over the k cores, and then "re-united" before each resampling step? Then the better performance of the particle casade would be a convincing argument. Another motivation would be to look at more realistic examples, in particular cases where the running time of simulating a single particle is very variable (such as in e.g. models in stochastic chemometrics, off the top of my head)Two more points: 1. in most cases, people are interested in on-line algorithms: i.e. datapoints are collected sequentially, and as soon as y_n is available, computations may resume to deliver the filtering distribution at time n, etc. Do I understand correctly that the proposed algorithm is not on-line any more (see 305-306)? (If yes, then this point should be mentioned; also perhaps it's easy to make it on-line again? 2. Why did you compare particle casade to CSMC??? Sorry, I really did not understand this. CSMC samples from the smoothing distribution (if you take the selected trajectory), and is not really meant to be a filtering algorithm??? Minor remarks: 27: first sentence is a bit unclear; it's oddly constructed.  262: posterior marginals: do you mean filtering marginals (conditional on data up to time n), or smoothing marginals (conditional up to final time N)? I guess the former, but your terminology seems to mean the latter. Also does the MSE correspond to the filterting expectation of the state in Figures 1 and 2? See also 396 "true posterior distribution". 428-430: sorry, I did not understand this part.