arxiv: 2604.03352 · v2 · submitted 2026-04-03 · 📊 stat.CO

Recognition: 2 theorem links

· Lean Theorem

On the complexity of standard and waste-free SMC samplers

Matti Vihola, Nicolas Chopin, Yvann Le Fay

Pith reviewed 2026-05-13 18:35 UTC · model grok-4.3

classification 📊 stat.CO

keywords sequential Monte CarloSMC samplersfinite sample boundswaste-free SMCtempering sequencesnormalising constantscomplexity analysis

0 comments

The pith

Finite sample error bounds are established for standard and waste-free SMC samplers on both expectations and normalising constants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives explicit finite-sample bounds on the error of sequential Monte Carlo samplers, covering both the standard and waste-free variants. These bounds apply first to arbitrary sequences of target distributions and then to the special case of tempering sequences. From the bounds the authors extract the computational complexity of the samplers as a function of the number of target distributions T in the general setting and the ambient dimension d under tempering. The resulting expressions are used to give concrete guidance on how to set the number of particles and other tuning parameters in practice.

Core claim

We establish 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 our results 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.

What carries the argument

Finite-sample error bounds obtained from uniform ergodicity of the Markov kernels together with bounded likelihood ratios along the sequence of distributions.

If this is right

The number of particles needed for a given error tolerance grows linearly with the number of target distributions T.
Under tempering the complexity scales explicitly with dimension d.
Waste-free and standard samplers admit comparable bounds, allowing direct comparison of their costs.
Practical tuning rules follow directly from balancing the derived bias and variance terms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same bounding technique could be applied to other particle-based methods that rely on similar mixing assumptions.
When the ergodicity conditions are only approximately satisfied the bounds still supply a useful diagnostic for when the sampler is likely to break down.
The explicit dependence on T suggests that adaptive choice of the number of tempering steps could be optimised against the derived cost.

Load-bearing premise

The Markov transition kernels must be uniformly ergodic and the successive distributions must satisfy bounded likelihood ratios or comparable mixing conditions.

What would settle it

Empirical error that fails to decay at the predicted rate with increasing particle count when the kernels are known to be uniformly ergodic and the likelihood ratios are bounded.

Figures

Figures reproduced from arXiv: 2604.03352 by Matti Vihola, Nicolas Chopin, Yvann Le Fay.

**Figure 2.** Figure 2: Relative error distributions (log-scale) for the estimators [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

read the original abstract

We establish 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 our results 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

New finite-sample bounds for SMC error and complexity, but they rest on mixing assumptions that may not deliver useful rates for typical high-d tempering targets.

read the letter

The main takeaway is that this paper derives explicit finite-sample bounds on the error of both standard and waste-free SMC samplers for expectations and normalizing constants, then converts those bounds into complexity statements with respect to T in the general case and d in the tempering case. They also extract some practical tuning advice from the rates. That combination is new; prior SMC work has bounds, but the waste-free extension and the explicit complexity scalings appear to be fresh. The organization, starting from arbitrary sequences before specializing to tempering, is clean and makes the results easier to apply. Practitioners who need to choose N or the number of steps without pure guesswork will get something concrete from the derived recommendations. The derivations follow the usual probabilistic route for SMC, which is fine as far as it goes. The soft spot is the assumptions. The bounds require uniform ergodicity of the kernels and bounded likelihood ratios between consecutive targets. For tempering sequences on non-log-concave or high-dimensional targets, those minorization constants often deteriorate with d, which can make the O(1/N) error and the resulting complexity claims loose or uninformative in practice. The abstract does not show a dimension-free fix, so the tempering complexity results may be mostly formal unless the full proofs supply something stronger. This is for people who implement or analyze SMC in statistical computing and want rigorous error control rather than heuristics. A reader who already knows the standard SMC literature will get the most out of it. The work shows clear thinking and direct engagement with the existing theory, so it deserves a serious referee even if the assumptions will need careful discussion in review.

Referee Report

1 major / 1 minor

Summary. The manuscript establishes finite-sample bounds on the error of standard and waste-free SMC samplers for estimating expectations and normalizing constants of target distributions. It first derives results for arbitrary sequences of distributions and then specializes to tempering sequences, using the bounds to obtain complexity scalings with respect to the number of targets T (general case) and dimension d (tempering case), together with practical implementation recommendations.

Significance. If the bounds hold under the stated assumptions on the kernels and targets, the work supplies concrete theoretical guidance on the computational cost of SMC methods, which are central to Bayesian computation and related fields. The explicit treatment of waste-free SMC and the derivation of complexity in both T and d are useful for practitioners choosing particle numbers and schedules.

major comments (1)

[tempering sequences analysis and complexity derivation] The finite-sample O(1/N) bounds and the resulting complexity scalings for tempering sequences rest on uniform ergodicity (or equivalent minorization) of the Markov transition kernels together with uniform bounds on the Radon-Nikodym derivatives between consecutive targets. For typical tempering sequences on non-log-concave targets these constants deteriorate exponentially in d, which would render the stated complexity guarantees in d vacuous for high-dimensional problems unless the paper supplies explicit dimension-independent minorization constants.

minor comments (1)

Ensure that the practical recommendations for end users are explicitly tied to the derived bounds rather than stated separately.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting an important point about the scope of our complexity results. We address the major comment below.

read point-by-point responses

Referee: The finite-sample O(1/N) bounds and the resulting complexity scalings for tempering sequences rest on uniform ergodicity (or equivalent minorization) of the Markov transition kernels together with uniform bounds on the Radon-Nikodym derivatives between consecutive targets. For typical tempering sequences on non-log-concave targets these constants deteriorate exponentially in d, which would render the stated complexity guarantees in d vacuous for high-dimensional problems unless the paper supplies explicit dimension-independent minorization constants.

Authors: We agree that the minorization constants (denoted ε in Assumption 3.1) and the uniform bounds on Radon-Nikodym derivatives (M in Assumption 4.2) are central to the O(1/N) bounds and the subsequent complexity scalings in d. The manuscript derives the complexity results conditionally on these quantities being independent of d; it does not claim to supply explicit dimension-independent minorization constants for arbitrary non-log-concave targets. For classes of targets and kernels where such constants can be shown to be O(1) in d (e.g., strongly log-concave distributions with suitable proposals or certain tempered distributions admitting dimension-free mixing), the stated scalings apply directly. In the revised manuscript we will add a clarifying paragraph in Section 4.3 that explicitly states the dependence on these constants, references the relevant literature on dimension-independent ergodicity, and notes the regimes in which the d-complexity guarantees remain informative. revision: partial

Circularity Check

0 steps flagged

Finite-sample bounds derived from external probabilistic inequalities with no self-referential reduction

full rationale

The paper establishes finite-sample error bounds for standard and waste-free SMC samplers by applying standard probabilistic inequalities to the resampling and mutation steps under explicit assumptions on the Markov kernels (uniform ergodicity or minorization) and the sequence of target distributions (bounded Radon-Nikodym derivatives). These assumptions are stated as external conditions rather than derived from the bounds themselves, and the subsequent complexity scalings in T and d follow directly from the resulting O(1/N) error expressions without any parameter fitting, renaming of known results, or load-bearing self-citations that reduce the central claim to its own inputs. The derivation chain remains self-contained against external benchmarks such as standard SMC convergence theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on domain-standard assumptions about the transition kernels and distribution sequence rather than new free parameters or invented entities.

axioms (1)

domain assumption Markov kernels satisfy conditions (uniform ergodicity or bounded Radon-Nikodym derivatives) sufficient for finite-sample error bounds to hold.
Standard technical assumption invoked in SMC convergence analysis to control particle degeneracy and obtain explicit constants.

pith-pipeline@v0.9.0 · 5399 in / 1184 out tokens · 55543 ms · 2026-05-13T18:35:28.277116+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
We establish finite sample bounds for the error of standard and waste-free SMC samplers... complexity of SMC samplers with respect to... T... or d... under spectral gap γ or mixing time τ
Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
Assume... Markov kernel K_t leaves π_{t-1} invariant... admits a spectral gap γ_t >0... mixing time τ(ξ,ω,K)

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

Q.(2024)

Andrieu, C.,Lee, A.,Power, S.andWang, A. Q.(2024). Explicit convergence bounds for Metropolis Markov chains: Isoperimetry, spectral gaps and profiles.The Annals of Applied Probability344022 –

work page 2024
[2]

Springer International Publishing, Cham

14, 15, 33 Bakry, D.,Gentil, I.andLedoux, M.(2014).Logarithmic Sobolev InequalitiesInAnalysis and Geometry of Markov Diffusion Operators. Springer International Publishing, Cham. 29 Beskos, A.,Crisan, D.andJasra, A.(2014). On the stability of sequential Monte Carlo methods in high dimensions.The Annals of Applied Probability24. 4 Beskos, A.,Crisan, D. O.,...

work page 2014
[3]

Normalizing constants of log-concave densities.Electronic Journal of Statistics12851 –

4 Brosse, N.,Durmus, A.andMoulines, ´E.(2018). Normalizing constants of log-concave densities.Electronic Journal of Statistics12851 –

work page 2018
[4]

J.andVacher, A.(2025)

4 Chehab, O.,Korba, A.,Stromme, A. J.andVacher, A.(2025). Provable Convergence and Limitations of Geometric Tempering for L angevin Dynamics. InThe Thirteenth In- ternational Conference on Learning Representations. 14 Chewi, S.(2025).Log-Concave Sampling. 16, 30 Chewi, S.,Lu, C.,Ahn, K.,Cheng, X.,Gouic, T. L.andRigollet, P.(2021). Opti- mal dimension depe...

work page 2025
[5]

Central limit theorem for sequential Monte Carlo methods and its appli- cation to Bayesian inference.Ann

MR1929161 4 Chopin, N.(2004). Central limit theorem for sequential Monte Carlo methods and its appli- cation to Bayesian inference.Ann. Statist.322385–2411. MR2153989 (2006b:60033) 4 34 Chopin, N.,Crucinio, F.andKorba, A.(2024). A connection between tempering and entropic mirror descent. InProceedings of the 41st International Conference on Machine Learni...

work page 2004
[6]

M.(2001)

5 Neal, R. M.(2001). Annealed Importance Sampling.Statistics and computing11125–139. 4 Paulin, D.(2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods.Electronic Journal of Probability201 –

work page 2001
[7]

Non-asymptotic Error Bounds for Sequential MCMC Methods in Multimodal Settings

27 Schweizer, N.(2012). Non-asymptotic Error Bounds for Sequential MCMC Methods in Multimodal Settings. 5

work page 2012