Source-linked AI summary
On adaptive resampling strategies for sequential Monte Carlo methods
Pierre Del Moral, Arnaud Doucet, Ajay Jasra
TL;DR
Adaptive SMC resampling times are computed online, but convergence theory has largely focused on deterministic resampling schedules. The paper combines semigroup techniques with an original coupling argument to transfer reference-algorithm results, establishing functional central limit theorems and uniform exponential concentration estimates.
Problem
Adaptive SMC methods use random resampling times computed from current particle approximations, while most theoretical results assume deterministic resampling times.
Method
The paper combines semigroup techniques with an original coupling argument to compare adaptive SMC with a reference algorithm using deterministic resampling times.
Results
The paper establishes functional central limit theorems and uniform exponential concentration estimates for adaptive SMC algorithms.
Takeaways & Limitations
The coupling transfers convergence results from the reference SMC algorithm to adaptive SMC, whose resampling times converge almost surely toward deterministic limits.
Takeaways & Limitations
The analysis cannot handle thresholds coinciding with adaptive criterion values, motivating randomized criteria thresholds; this issue is absent in many applications where the event has probability zero.
Abstract
from arXiv · showhide
Sequential Monte Carlo (SMC) methods are a class of techniques to sample approximately from any sequence of probability distributions using a combination of importance sampling and resampling steps. This paper is concerned with the convergence analysis of a class of SMC methods where the times at which resampling occurs are computed online using criteria such as the effective sample size. This is a popular approach amongst practitioners but there are very few convergence results available for these methods. By combining semigroup techniques with an original coupling argument, we obtain functional central limit theorems and uniform exponential concentration estimates for these algorithms.
1. Introduction
SMC methods approximate sequences of probability distributions using particles, importance sampling, and resampling. This paper analyzes adaptive methods whose online, random resampling times create a gap in existing convergence theory and establishes convergence results through coupling.
- SMC methods: SMC methods approximate target probability distributions with particles that evolve through importance sampling and resampling.These methods are used across engineering, statistics, and physics.
- Adaptive resampling: Resampling is essential for time-uniform convergence, but excessive resampling reduces the number of distinct particles.The trade-off motivates triggering resampling only when necessary.
- Adaptive resampling: Practical SMC implementations select resampling times online by monitoring criteria such as particle-approximation quality and triggering resampling at a threshold.This adaptive strategy has been widely adopted since its original proposal.
- Theoretical gap: Adaptive resampling times are random, whereas most existing SMC theory assumes deterministic resampling times.The paper addresses this mismatch using a coupling argument.
- Main contribution: The coupling makes the difference between adaptive SMC and a reference algorithm with deterministic resampling times exponentially small in the particle number.This permits transfer of convergence results and yields functional central limit theorems and improved exponential concentration estimates.
2. Adaptive SMC algorithms and main results
Adaptive SMC methods trigger resampling online when particle-based criteria indicate it is needed, making resampling times random. The paper analyzes these algorithms by comparing them with a deterministic-time reference system through exponential concentration and coupling results.
- Adaptive resampling: Adaptive SMC triggers resampling when a criterion computed from the current particle approximation is satisfied, rather than at every time step.This avoids the wastefulness associated with resampling at each step.
- Reference process: Adaptive resampling times depend on the current SMC approximation and are therefore random, whereas the reference algorithm uses deterministic times obtained from limiting criteria.The deterministic times replace empirical criteria with their limiting values as the number of particles grows.
- Adaptive resampling: The squared coefficient of variation criterion is equivalent to resampling when the effective sample size falls below a prescribed threshold.The paper also discusses an entropy-based criterion using the relative entropy of the empirical measure and its weighted version.
- Main results: The paper’s first main result provides non-asymptotic exponential concentration estimates for SMC approximations under stated regularity conditions.The estimates apply to functions with bounded oscillation and, under additional conditions, to marginal measures over intervals between deterministic resampling times.
- Main results: The second main result is an exponential coupling theorem showing that adaptive and deterministic-time particle systems coincide over finite horizons except with exponentially small probability.The result holds for almost every realization of absolutely continuous threshold parameters and transfers estimates from the reference SMC algorithm to the adaptive one.
3. Description of the models
The paper formulates adaptive SMC through Feynman–Kac flows on excursion-valued state spaces, then defines resampling times using functional criteria and thresholds.
- Feynman–Kac model: The model combines Markov transitions with bounded potential functions to define normalized and unnormalized Feynman–Kac measure flows.The Boltzmann–Gibbs transformation supplies the weighting step, followed by Markov prediction.
- Semigroup formulation: A linear Feynman–Kac semigroup represents the unnormalized measures, while a nonlinear semigroup represents the normalized flow.These semigroups organize the propagation and normalization operations used in the analysis.
- Excursion model: The excursion construction embeds variable-length path segments into Markov state spaces whose potentials encode the corresponding path weights.This construction preserves the recursive Feynman–Kac updating and prediction equations.
- Adaptive criteria: Resampling times are defined as the first future time when a functional criterion reaches a threshold interval.The paper illustrates this construction with squared coefficient-of-variation and relative-entropy criteria.
- Adaptive criteria: The criteria measure weight variability or entropy distance and satisfy a Lipschitz-type regularity condition under the stated potential assumptions.These regularity properties connect empirical criteria to their limiting functional versions.
4. Convergence analysis of the reference SMC algorithm
The reference SMC algorithm is analyzed through its particle updating and prediction structure, Feynman–Kac semigroup bounds, and martingale-based error decompositions. Under mixing and regularity conditions, the analysis yields non-asymptotic and time-uniform concentration estimates.
- Particle representation: The particle system replaces distribution-level updating and prediction with resampling and mutation transitions while retaining the reference Feynman–Kac structure.Particles and their ancestral paths provide the empirical approximation analyzed throughout the section.
- Semigroup analysis: Semigroup and mixing assumptions control the propagation of local sampling errors and can make the relevant bounds uniform in the final time horizon.The uniformity depends on regularity conditions for the Markov transitions and associated semigroup quantities.
- Error decomposition: The empirical approximation admits martingale and first-order nonlinear-semigroup decompositions used to derive bias and Lm error bounds.These decompositions isolate local random-field errors and support the subsequent concentration analysis.
- Concentration results: Theorem 4.6 provides exponential concentration estimates for bounded-oscillation test functions, including a uniform form under additional mixing conditions.The estimates apply to particle approximations at arbitrary time parameters under the stated assumptions.
- Intermediate-time bounds: The same concentration analysis extends to intermediate-time marginal particle measures, with finite constants depending on the time parameter.Finite-support criteria yield an additional concentration inequality with two finite constants.
5. Asymptotic analysis
The asymptotic analysis couples adaptive and reference particle systems through their resampling times. Away from threshold ties, the coupling yields exponential estimates; randomized thresholds remove the problematic equality case almost surely.
- Coupling construction: The coupling construction compares adaptive particle resampling times with deterministic reference times through events on which the two systems coincide.The proof proceeds inductively over successive resampling stages.
- Threshold separation: The analysis assumes threshold parameters avoid equality with the limiting adaptive criteria values.Under this separation condition, the reference and adaptive particle models can be controlled through the coupling argument.
- Technical boundary: Threshold ties cannot be handled by the analysis because both empirical criteria and particle approximations must then be controlled simultaneously.This is identified as a technical issue rather than a general failure of adaptive SMC.
- Randomized criteria: Absolutely continuous randomized thresholds make the separation from limiting criterion values strictly positive for almost every threshold realization.This removes the equality case used as the main technical boundary of the analysis.
- Asymptotic result: For almost every randomized-threshold realization, the paper obtains exponential estimates for the coupled adaptive and reference particle models.The result is stated with finite constants that may depend on the number of resampling stages.
6. A functional central limit theorem
This section develops functional central limit results for the adaptive SMC approximation by decomposing global fluctuations into local errors and controlling the remainder. The resulting fields converge to centered Gaussian limits, including for the online adaptive model.
- 6.3. Adaptive approximation: The same Gaussian convergence applies, for almost every threshold realization, to the online adaptive approximation and related mixtures of random-field sequences.The fluctuation analysis is explicitly connected to the online adaptive particle model and its path-space occupation measures.
- 6.2. Functional central limit theorems: For fixed time horizon n, the local fields V^N_p converge to n independent, centered Gaussian random fields V_p.The covariance of each limiting field is specified through the associated kernel and test functions.
- 6.1. A direct approach: The functional fluctuation analysis decomposes the fields into local fluctuation errors and remainder random fields.The semigroup Dp,n organizes the propagation of local errors, while the remainder terms are shown to vanish asymptotically.
- 6.1. A direct approach: The remainder random fields converge in law to the null random field as N increases, so the limiting fluctuations follow from the functional theorem.This identifies the remainder as asymptotically negligible in the finite-distribution sense used here.
- 6.2. Functional central limit theorems: For fixed time horizon n, the global fields W^N_n converge in law to centered Gaussian random fields W_n.The limiting fields are represented through the semigroup propagation of the local Gaussian fluctuations.
- 6.4. Related work: The adaptive result addresses a gap in prior convergence analyses, which generally treated resampling times as deterministic or did not account for their randomness.The cited related-work discussion identifies only limited previous convergence results for adaptive SMC schemes.
Appendix
The appendix supplies proof steps for semigroup identities and inductive decompositions used in the fluctuation analysis.
- Proof of Lemma 4.4: The proof rewrites the relevant operator expression using Qp,n and the normalized quantities Gp,n,η and Pp,n.It uses the identity η(Gp,n,η) = 1 in the derivation.
- Proof of Lemma 6.3: The decomposition in equation (6.2) is established by induction on n, beginning with the case n = 0.The induction step uses the convention Dn+1,n+1 = I.