@article{YL-WW-KD-JL:2021,
  title={Stratification and Optimal Resampling for Sequential {M}onte {C}arlo},
  author={Li, Yichao and Wang, Wenshuo and Deng, Ke and Liu, Jun S},
  journal = {Biometrika},
  year = {2021},
  month = {02},
  abstract = "{Sequential Monte Carlo algorithms have been widely accepted as a powerful computational tool for making inference with dynamical systems. A key step in sequential Monte Carlo is resampling, which plays a 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 the one-dimensional cases, we show that optimal transport resampling is equivalent to stratified resampling on the sorted particles, and they both minimize the resampling variance as well as the expected squared energy distance between the original and resampled empirical distributions. In general d-dimensional cases, if the particles are first sorted using the Hilbert curve, we show that the variance of stratified resampling is O(m-(1+2/d)), an improved rate compared to the previously known best rate O(m-(1+1/d)), where m is the number of resampled particles. We show this improved rate is optimal for ordered stratified resampling schemes, as conjectured in Gerber et al. (2019).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).}",
  issn = {0006-3444},
  doi = {10.1093/biomet/asab004},
  url = {https://doi.org/10.1093/biomet/asab004},
  note = {asab004},
  eprint = {https://academic.oup.com/biomet/advance-article-pdf/doi/10.1093/biomet/asab004/36226556/asab004.pdf},
}