Nicolas Chopin will participate to the workshop on Advances in MCMC Methods and present his paper “What is actual the complexity of tempering (SMC)?

What is actual the complexity of tempering (SMC) ? 
There is some discrepancy in the literature regarding the complexity of tempering with respect to d, the dimension of the sampling space. The complexity is partly determined by the length of the temperature ladder, that is, the sequence of tempering exponents 0=lambda_0 < … < lambda_T = 1. In the AIS (annealed importance sampling) literature, it is often recommended to take T = O(d). Some SMC (Sequential Monte Carlo) papers instead suggest that ESS-based criteria leads to T=O(d^{1/2}).
In this talk, I will present results from both a recent paper (with Francesca Crucinio and Anna Korba, ICML 2024) and some preliminary work (with Yvann Le Fay and Matti Vihola) that shed light on this discrepancy. Basically, for moments with respect to the target distribution, T=O(d^{1/2})$ suffices to leads to estimates with variance O(1). However, for the normalising constant, variance is then O(T) = O(d^{1/2})$.
The actual complexity of the considered sampler will also depend, of course, on the mixing properties of the MCMC kernels used to rejuvenate the particles. I will explain how we can exploit some existing, non-asymptotic results on such kernels to obtain the overall complexity of the sampler.