ON BACKWARD SMOOTHING ALGORITHMS

• 成果类型: Article
• 署名作者: Dau, Hai-dang; Chopin, Nicolas
• 署名单位: Institut Polytechnique de Paris; ENSAE Paris
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2324
• 发表日期: 2023
• 页码: 2145-2169
• 关键词: feynman-kac; particle

摘要

In the context of state-space models, skeleton-based smoothing algo-rithms rely on a backward sampling step, which by default, has a O(N-2) complexity (where N is the number of particles). Existing improvements in the literature are unsatisfactory: a popular rejection sampling-based approach, as we shall show, might lead to badly behaved execution time; another rejec-tion sampler with stopping lacks complexity analysis; yet another MCMC-inspired algorithm comes with no stability guarantee. We provide several re-sults that close these gaps. In particular, we prove a novel nonasymptotic stability theorem, thus enabling smoothing with truly linear complexity and adequate theoretical justification. We propose a general framework, which unites most skeleton-based smoothing algorithms in the literature and allows to simultaneously prove their convergence and stability, both in online and offline contexts. Furthermore, we derive, as a special case of that frame-work, a new coupling-based smoothing algorithm applicable to models with intractable transition densities. We elaborate practical recommendations and confirm those with numerical experiments.