Negative association, ordering and convergence of resampling methods

Mathieu Gerber, Nicolás Chopin, Nick WhiteleyThe Annals of Statistics 2019 · DOI

Abstract

We study convergence and convergence rates for resampling schemes in Sequential Monte Carlo (SMC) methods. Our primary contributions include a general consistency theorem based on the property of negative association (NA), which establishes the almost-sure weak convergence of Kitagawa’s stratified resampling. We introduce a new resampling algorithm based on the Srinivasan Sampling Process (SSP) that ensures negative association and order-invariance. Furthermore, we confirm that ordering particles via Hilbert curves in $\mathbb{R}^d$ achieves a variance of the resampling error at a rate of $\mathcal{O}(N^{-(1+1/d)})$, surpassing the standard $\mathcal{O}(N^{-1})$ rate.

Introduction

Sequential Monte Carlo (SMC) methods, or particle filters, represent probability distributions through a set of weighted particles. A recurring challenge in these methods is weight degeneracy, where a small number of particles eventually carry the majority of the total weight. Resampling is the standard solution, involving the replication of high-weight particles and the removal of low-weight ones to maintain a representative sample.

While multinomial resampling is theoretically straightforward, it introduces significant Monte Carlo noise. Practitioners often turn to stratified or systematic resampling for better empirical performance. However, systematic resampling lacks a rigorous proof of convergence and is sensitive to the input order of particles. This paper addresses these gaps by providing a unified framework for consistency and introducing more robust, faster-converging algorithms.

Negative Association and Consistency

The core theoretical contribution of this work centers on Negative Association (NA). A set of random variables is negatively associated if the probability of them being "large" simultaneously is lower than if they were independent. This property prevents the "clumping" of particles that leads to high variance.

The authors establish a General Consistency Theorem: any resampling scheme satisfying the NA property achieves almost-sure weak convergence. This framework allows for the first formal proof of convergence for Kitagawa’s stratified resampling. Conversely, the paper demonstrates that systematic resampling fails to satisfy NA, explaining its potential for instability and dependence on particle ordering.

The SSP Resampling Algorithm

To bridge the gap between the low variance of systematic resampling and the theoretical reliability of stratified resampling, the authors introduce SSP Resampling. Based on the Srinivasan Sampling Process—a stochastic rounding technique—this algorithm satisfies the NA property.

Unlike systematic resampling, SSP is order-invariant. It provides the same statistical guarantees regardless of how the input particles are sorted, making it a more robust choice for complex filtering tasks. SSP maintains a computational complexity of $\mathcal{O}(N)$, ensuring it remains a practical drop-in replacement for existing methods.

Hilbert Curve Ordering

In one-dimensional state spaces, sorting particles by their value before resampling is a known technique to reduce variance. The authors extend this to higher dimensions ($d > 1$) by utilizing Hilbert space-filling curves.

By mapping multi-dimensional particle states onto a 1D line while preserving local spatial relationships, the Hilbert curve allows the resampling process to maintain spatial "stratification." The authors prove that for Hilbert-ordered stratified resampling, the variance of the resampling error is $\mathcal{O}(N^{-(1+1/d)})$. This is a significant improvement over the standard $\mathcal{O}(N^{-1})$ rate, particularly in low-to-moderate dimensions.

Results and Discussion

The theoretical findings are supported by numerical experiments using synthetic linear Gaussian state-space models. Over 500 time steps with $N = 2^{13}$ particles, the results indicate:

  • Superiority of SSP: SSP resampling generally outperforms standard stratified resampling, particularly when paired with guided proposals.
  • Convergence Rates: The predicted $\mathcal{O}(N^{-(1+1/d)})$ convergence rate for Hilbert-ordered schemes is empirically observed, confirming Kitagawa’s long-standing conjecture.
  • Computational Trade-offs: While the resampling step remains $\mathcal{O}(N)$, the necessary sorting for Hilbert ordering introduces an $\mathcal{O}(N \log N)$ overhead.

Conclusion and Future Work

This research provides the theoretical foundation for advanced resampling techniques in SMC. By identifying Negative Association as the key to consistency and Hilbert curves as the path to faster convergence, the authors offer a roadmap for more efficient particle filters. Future work remains to be done in extremely high-dimensional spaces where the $1/d$ benefit diminishes, and in exploring the interaction between these resampling schemes and Auxiliary Particle Filters (APF).

Summary updated

Abstract

We study convergence and convergence rates for resampling schemes. Our first main result is a general consistency theorem based on the notion of negative association, which is applied to establish the almost-sure weak convergence of measures output from Kitagawa's (1996) stratified resampling method. Carpenter et al's (1999) systematic resampling method is similar in structure but can fail to converge depending on the order of the input samples. We introduce a new resampling algorithm based on a stochastic rounding technique of Srinivasan (2001), which shares some attractive properties of systematic resampling, but which exhibits negative association and therefore converges irrespective of the order of the input samples. We confirm a conjecture made by Kitagawa (1996) that ordering input samples by their states in $\mathbb{R}$ yields a faster rate of convergence; we establish that when particles are ordered using the Hilbert curve in $\mathbb{R}^d$, the variance of the resampling error is ${\scriptscriptstyle\mathcal{O}}(N^{-(1+1/d)})$ under mild conditions, where $N$ is the number of particles. We use these results to establish asymptotic properties of particle algorithms based on resampling schemes that differ from multinomial resampling.
BibTeX
@article{gerber2019negative,
  author = {Mathieu Gerber and Nicolás Chopin and Nick Whiteley},
  title = {{Negative association, ordering and convergence of resampling methods}},
  journal = {The Annals of Statistics},
  year = {2019},
  doi = {10.1214/18-aos1746},
}
Figure