On the complexity of standard and waste-free SMC samplers
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "On the complexity of standard and waste-free SMC samplers".
Paper summary: Tom: So, to recap, the paper "On the complexity of standard and waste-free SMC samplers" is focused on setting finite sample bounds for errors in both standard and waste-free SMC samplers. They cover estimates for expectations and normalizing constants across any sequence of distributions, specializing their work for tempering sequences.
Jane: The core claim they're making is that they derive the complexity of these SMC samplers based on parameters like T or d, which tells us how much computation we need. This is important because it gives us a concrete measure of what's going to happen computationally.
Lu: They use these bounds to recommend practical implementation strategies for end users, which moves it beyond just proving things mathematically and into the realm of real-world applicability.
Meng: I wonder how this changes things for production deployment? Are we talking about a massive increase in required computational resources if we switch from standard to waste-free?
Tom: They compare standard and waste-free SMC samplers, and they show that the key difference is how they define the pool of candidates for reweighting and resampling steps. Standard SMC only resamples the end point, while waste-free SMC resamples all N equals M times P iterates of the chains.
Jane: That seems like a big difference in how much data they're using for each step. The numerical experiments Dau and Chopin did show that waste-free SMC tends to outperform standard SMC samplers.
Lalam: So, the paper is essentially saying that by keeping more samples around, even if it adds complexity, you might get better estimates for the distributions we're interested in.
Conclusion: Tom: So we've looked at this paper on the complexity of standard and waste-free SMC samplers. The title itself sets up a comparison between these two methods and their computational cost.
Jane: And what they claim is that they establish finite sample bounds for the error of both types of samplers, covering expectations and normalizing constants. They show how to derive complexity based on parameters like T or d, and they provide practical recommendations for implementation.
Lu: The implication is that we have a way to understand the computational cost precisely before we even start running these complex algorithms on real problems.
Meng: For someone shipping models, this means we can estimate resource needs more accurately than just guessing based on theoretical complexity alone.
Tom: It’s about moving from just knowing an algorithm exists to knowing exactly how much it will cost us in Markov steps, which is what complexity means here.
Jane: And they point towards the greedy variant of waste-free SMC as a practical recommendation for end users, which seems like a good starting point for deployment.
Lalam: It sounds like the paper gives us a solid foundation to build something that’s both theoretically sound and computationally sensible.
CREST · ENSAE · IP Paris · Department of Mathematics and Statistics, University of Jyvaskyla
stat.CO
Submitted: 2026-04-03
Updated: 2026-11-18
Code: https://github.com/ylefay/jaxSMC
The gist: On the complexity of standard and waste-free SMC samplers establishes finite sample bounds for the error of standard and waste-free SMC samplers Our results cover estimates of both expectations and…
Key concepts
- Standard SMC
- In this method, only the final state of the chains is reweighted and resampled. It is a baseline algorithm used in sequential Monte Carlo sampling to approximate target distributions.
- Waste-free SMC
- This alternative involves reweighting all N iterates of the chains before resampling M particles. Numerical experiments suggest this method tends to outperform standard SMC samplers.
- Complexity (Query Complexity)
- This measures the number of Markov steps required by an algorithm in this context, specifically the product TMP for Algorithms 1 and 2. It quantifies how many steps are needed to achieve a desired level of accuracy.
- Normalizing Constant ($Z_T$)
- These constants are crucial for accurately estimating the target distribution's probability density function. The paper provides bounds on how accurately waste-free SMC can estimate these constants.
Terminology
Summary
On the complexity of standard and waste-free SMC samplers establishes finite sample bounds for the error of standard and waste-free SMC samplers Our results cover estimates of both expectations and normalising constants of the target distributions We consider first an arbitrary sequence of distributions, and then specialise our results to tempering sequences We use these bounds to derive the complexity of SMC samplers with respect to the parameters of the problem, such as T, the number of target distributions, in the general case, or d, the dimension of the ambient space, in the tempering case We use these bounds to derive practical recommendations for the implementation of SMC samplers for end users. p. 0
Waste-free versus standard Sequential Monte Carlo
The key difference between the two algorithms is how they define the pool of candidates for the reweighting and resampling steps In standard SMC, only the end point Xm,P t of the chains are reweighted and resampled In waste-free SMC, all the N = MP iterates of these chains are reweighted; then M particles are resampled out of these N candidates. Dau and Chopin (2022), who introduced waste-free SMC samplers, show in their numerical experiments that they tend to outperform standard SMC samplers. p. 1
Summary of main results
The complexity bounds obtained in this paper depend on the type of sequence of distributions (arbitrary, or tempering), the type of the estimates, i.e. (1) or (2), and the assumptions on the Markov kernels. p. 2 Complexity (a. p. 0k.a. query complexity) means number of Markov steps in our context, i. p. 2e., the product TMP for Algorithms 1 and 2. p. 2 Table 1 summarizes the O(·) complexities for SMC samplers in terms of T (number of target distributions), d (ambient dimension, X = Rd), γ (min of spectral gaps of Markov kernels) and τ (mixing-time of the kernels). p. 2
Moment Estimation Bounds
For moment estimates, we obtain a complexity for waste-free SMC which is smaller than for standard SMC by a factor log(T ε−2η−1). In case one is interested only in moments with respect to πT−1, we show it is possible to design a greedy variant of waste-free SMC, where P is constant at times t < T, and then scales like O(ε−2) at iteration T. p. 2 In words, in order to estimate accurately (i. p. 6e. ε≪1) moments relative to πT−1, only PT needs to scale like ε−2, while the previous Pt, t < T, may stay constant (relative to ε). p. 6
Normalising Constant Bounds
We now turn to the problem of estimating the normalising constants ZT. A first, naive approach consists in directly combining the concentration bounds obtained in the previous section with a union bound over t = 0,. p. 7.., T. Theorem 3.4 shows that waste-free SMC (Algorithm 2) returns ZbT such that ZbT /ZT − 1 < ε with probability at least 3/4. p. 7 The complexity for this bound is O T 4 γ squared. p. 4
Application to tempering and other scenarios
For geometric tempering on log-concave and smooth distributions, the complexity bounds given below are obtained. For estimating ZT with failure probability η = 1/4, O(d squared ε−2) using Algorithm 2 is compared against O(d 3/2 κ 5 ε−2) for the product-of-medians estimator given by Algorithm 4. p. 8
Conclusion and Recommendations
For end users, we recommend the greedy variant of waste-free SMC, Algorithm 3. If they are only interested in moments with respect to πT−1, it is sufficient to take Pt large enough relative to the mixing time of kernel Kt. p. 9 For tempering, the best complexity we managed to obtain, i. p. 2e. O˜(d squared ε−2), for estimating ZT was for standard SMC, using MALA kernels. p. 2 We recommend instead to keep P fixed across iterations. p. 6 The standard estimator ZˆT is unbiased, whereas Zˆmed T is more robust when the reweighting functions Gt are heavy-tailed. p. 8
Estimate Algorithm Complexity
The complexity bounds for estimating ZT within relative precision ε with failure probability ≤ 1/4, under log-concave and smooth targets are summarized in Table 3. The median estimator saves a factor ZˆT med WF-SMC (RWMH) d cubed κ 5 ε−2 SMC (MALA) d 5/2 κ 4 ε−2. p. 4
Implementation Details
The implementation of the numerical experiments is available at https://github.com/ylefay/jaxSMC; SMC and waste-free SMC are also implemented in https://github. p. 0com/nchopin/particles. p. 0 The paper discusses the practical implications of these results to end users at the end of the paper Section 7. p. 3
Future Work
A direction for future work is to determine how concentration scales jointly with the number of parallel chains M and the chain length P. Our current finite-sample analysis of waste-free SMC essentially treats M as a constant and does not yield sharp improvements as M increases. p. 3 The limitation stems from dependence induced by resampling, and it remains unclear whether one can recover an effective 1/(MP) variance rate rather than a 1/P rate.
Acknowledgments
YLF acknowledges a CREST PhD scholarship MV was supported by Research Council of Finland (Finnish Centre of Excellence in Randomness and Structures, grants 346311 and 364216). We are grateful to Daniel Paulin and Pierre Jacob for insightful discussions and remarks.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Waste-free SMC samplers can be used for estimating moments relative to target distributions with a complexity bound of O(T gamma squared log T eta) when Markov kernels admit a spectral gap. This allows AI systems to estimate expected values of functions on sequences of distributions more efficiently than standard SMC.
-
The greedy variant of waste-free SMC can reduce the complexity for moment estimates to O(T gamma log T eta + 1 / gamma squared log T eta). This means AI systems can achieve faster convergence for estimating moments by making the chain length P scale appropriately at each iteration.
-
Waste-free SMC samplers provide finite sample bounds for normalising constant estimates, such as ZT/ZT-1 < epsilon with probability at least 1 minus eta. This enables AI systems to estimate the normalization constants of target distributions with quantifiable accuracy guarantees.
-
For Gaussian base measures and log-concave smooth targets, the complexity for estimating ZT using waste-free SMC is O(d squared epsilon-2 gamma 2). This provides a specific performance metric for AI systems targeting these distribution classes.
-
The product-of-medians estimator can estimate normalising constants with a complexity of O(d 3/kappa cubed epsilon-2 gamma squared log T eta) for tempered sequences under certain conditions. This offers an alternative method for estimating normalization constants with potentially better robustness to heavy-tailed reweighting functions.
-
The analysis provides practical recommendations: if only moments relative to piT-1 are needed, use the greedy waste-free SMC variant, and if normalising constants are required, keep P fixed across iterations for tempering scenarios.
Related papers
- Sticky Manifold Piecewise Deterministic Monte Carlo for Bayesian Model Averaging
- A perturbation theory for Feynman-Kac models and their particle interpretations
- Fast Functional Clustering via Closed-Form Covariance Updates
- A fast non-reversible sampler for Bayesian mixture models
- Inventory and Assortment Optimization under General Choice: A Unified Approximation Framework
- Least squares variational inference