The divide-and-conquer sequential Monte Carlo algorithm: theoretical properties and limit theorems

Juan Kuntz, Francesca R. Crucinio, Adam M. Johansen

Abstract

This paper provides a comprehensive characterization of the theoretical properties of the divide-and-conquer sequential Monte Carlo (DaC-SMC) algorithm. We establish it as a mathematically rigorous method by demonstrating that it possesses the same fundamental properties as conventional sequential Monte Carlo (SMC) algorithms, including consistency, asymptotic normality, and unbiasedness of unnormalized estimates. Furthermore, we show that DaC-SMC is more statistically efficient than its direct SMC analogues under comparable conditions.

Introduction

Sequential Monte Carlo (SMC) methods, or particle filters, have long been the standard for approximating complex, high-dimensional probability distributions. Traditionally, these algorithms evolve linearly, which can lead to inefficiencies when dealing with models that possess inherent hierarchical structures or can be decomposed into independent sub-problems.

Divide-and-Conquer SMC (DaC-SMC) was proposed to address these limitations by recursively partitioning a large inference problem into smaller, manageable sub-problems organized in a tree structure. While DaC-SMC has shown empirical success, it previously lacked a rigorous theoretical foundation. This work fills that gap, proving that the algorithm is a well-founded statistical tool with predictable asymptotic behavior.

The DaC-SMC Framework

The core of DaC-SMC lies in its departure from the linear progression of standard SMC. Instead, it utilizes a tree-based decomposition and product-form estimators.

Tree Decomposition

The target distribution is mapped onto a tree where the leaves represent simple sub-problems and internal nodes represent the merging of these sub-problems. This structure allows the algorithm to process independent components of a model in parallel before combining them.

Product-Form Estimators

A critical innovation in DaC-SMC is the use of product-form estimators during the merging process. When combining $K$ independent sets of $N$ particles, a standard approach might only utilize $N$ pairs. In contrast, a product-form estimator considers all $N^K$ possible permutations. This "fork-and-join" approach significantly increases the effective sample size and reduces variance without requiring additional simulations, effectively providing "more bang for your buck" from the same particle count.

Theoretical Guarantees

By adapting classical SMC proof techniques—such as the Marcinkiewicz-Zygmund inequality and Feynman-Kac formulae—to the tree structure, we establish several key limit theorems:

  1. Consistency (Theorems 1 & 2): We prove that particle approximations in DaC-SMC converge almost surely to the true target distributions as the number of particles $N$ approaches infinity.
  2. Unbiasedness (Theorem 3): We demonstrate that the algorithm produces unbiased estimates of normalizing constants, such as marginal likelihoods, which is essential for model selection and Bayesian inference.
  3. Central Limit Theorem (Theorem 6): We characterize the rate of convergence as $\sqrt{N}$ and provide explicit expressions for the asymptotic variance, confirming that errors follow a predictable normal distribution.

Statistical Efficiency and Optimality

One of the most significant findings is the formal proof of statistical efficiency. Theorem 9 establishes that DaC-SMC is more statistically efficient than its direct SMC analogue (Auxiliary SMC) under comparable conditions. This efficiency stems from the algorithm's ability to exploit conditional independence within the model structure.

We also derive expressions for "locally optimal" intermediate targets and proposal kernels. While these choices minimize asymptotic variance for normalizing constants, we note a subtle distinction from standard SMC: these optimal choices do not necessarily lead to zero finite-sample variance, highlighting the unique dynamics of the tree-based merge steps.

Practical Considerations and Limitations

Despite its statistical advantages, DaC-SMC introduces a computational trade-off. The merging of nodes carries a cost of $O(N^d)$, where $d$ is the number of children per node. While "lightweight" variants can reduce this to $O(N)$, they may also diminish the statistical gains.

Furthermore, the effectiveness of the algorithm is tied to the model's structure. DaC-SMC performs best on models with product-like or hierarchical structures. For highly coupled models, the "corrections" required during the merge phase may negate the benefits of the divide-and-conquer approach. The question of how to optimally construct the decomposition tree for an arbitrary model remains an open area for future research.

Conclusion

This work elevates DaC-SMC from a successful heuristic to a mathematically rigorous methodology. By establishing its consistency, unbiasedness, and superior statistical efficiency, we provide practitioners with the theoretical confidence to apply divide-and-conquer strategies to complex hierarchical Bayesian models. Future work will focus on automating tree construction and integrating adaptive resampling techniques to further enhance the algorithm's practicality.

Summary updated

Abstract

We provide a comprehensive characterisation of the theoretical properties of the divide-and-conquer sequential Monte Carlo (DaC-SMC) algorithm. We firmly establish it as a well-founded method by showing that it possesses the same basic properties as conventional sequential Monte Carlo (SMC) algorithms do. In particular, we derive pertinent laws of large numbers, $L^p$ inequalities, and central limit theorems; and we characterize the bias in the normalized estimates produced by the algorithm and argue the absence thereof in the unnormalized ones. We further consider its practical implementation and several interesting variants; obtain expressions for its globally and locally optimal intermediate targets, auxiliary measures, and proposal kernels; and show that, in comparable conditions, DaC-SMC proves more statistically efficient than its direct SMC analogue. We close the paper with a discussion of our results, open questions, and future research directions.
BibTeX
@article{kuntz2024divide,
  author = {Juan Kuntz and Francesca R. Crucinio and Adam M. Johansen},
  title = {{The divide-and-conquer sequential Monte Carlo algorithm: theoretical properties and limit theorems}},
  journal = {The Annals of Applied Probability},
  year = {2024},
  doi = {10.1214/23-aap1996},
}
Figure