Stratification and optimal resampling for sequential Monte Carlo

Sequential Monte Carlo algorithms are widely accepted as powerful computational tools for making inference with dynamical systems. A key step in sequential Monte Carlo is resampling, which plays the role of steering the algorithm towards the future dynamics. Several strategies have been used in practice, including multinomial resampling, residual resampling, optimal resampling, stratified resampling and optimal transport resampling. In one-dimensional cases, we show that optimal transport resampling is equivalent to stratified resampling on the sorted particles, and both strategies minimize the resampling variance as well as the expected squared energy distance between the original and resampled empirical distributions. For general d-dimensional cases, we show that if the particles are first sorted using the Hilbert curve, the variance of stratified resampling is O(m(-(1+2/d))), an improvement over the best previously known rate of O(m(-(1+1/d))), where m is the number of resampled particles. We show that this improved rate is optimal for ordered stratified resampling schemes, as conjectured in . We also present an almost-sure bound on the Wasserstein distance between the original and Hilbert-curve-resampled empirical distributions. In light of these results, we show that for dimension d>1 the mean square error of sequential quasi-Monte Carlo with n particles can be O(n(-1-4/{d(d+4)})) if Hilbert curve resampling is used and a specific low-discrepancy set is chosen. To our knowledge, this is the first known convergence rate lower than o(n(-1)).

Automated summary

Sequential Monte Carlo algorithms are powerful tools for inference with dynamical systems. Resampling is a key step in the algorithm, with different strategies such as stratified resampling and optimal transport resampling used in practice. This study shows the equivalence of optimal transport resampling and stratified resampling in one-dimensional cases and demonstrates an improved variance rate for stratified resampling in general d-dimensional cases. The study also presents bounds on the Wasserstein distance and convergence rates for sequential quasi-Monte Carlo with Hilbert curve resampling.