Event Details

Statistics seminar in the School of Mathematical Sciences.

Title: Mixing time of the conditional backward sampling particle filter

Abstract: The conditional backward sampling particle filter (CBPF; also known as the particle Gibbs with ancestor sampling, PGAS) is a powerful Markov chain Monte Carlo sampler for general state space hidden Markov model smoothing. It was proposed as an improvement over the conditional particle filter, which is known to have an O(T^2) computational time complexity under a general 'strong mixing' assumption of the model, where T is the time horizon. We provide the first proof that the CBPF admits an O(T log T) computational complexity under strong mixing, complementing strong empirical evidence of the superiority of the CBPF in practice. In particular, the CBPF's mixing time is upper bounded by O(log T), for any sufficiently large number of particles N that depends only on the mixing constants and not T. We show that an O(log T) mixing time is optimal. The proof involves the analysis of a novel coupling of two CBPFs, which involves a maximal coupling of two particle systems at each time instant. The coupling is implementable, and thus can also be used to construct unbiased, finite variance, estimates of functionals which have arbitrary dependence on the latent state's path, with a total expected cost of O(Tlog T).

The talk is based on joint work with Joona Karjalainen, Sumeetpal S. Singh and Anthony Lee: https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.org%2F10.1093%2Fjrsssb%2Fqkaf078&data=05%7C02%7Csherlocc%40live.lancs.ac.uk%7C6332f0b43a7e431afaff08dea0741e15%7C9c9bcd11977a4e9ca9a0bc734090164a%7C0%7C0%7C639124617752097719%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=M2XCa7P0LO2FGKDK1WREGYP1cx3quMrynRF5W0S2eUg%3D&reserved=0