On backward smoothing algorithms

DOI10.1214/23-AOS2324arXiv2207.00976OpenAlexW4389815315MaRDI QIDQ6183776FDOQ6183776

Authors: Hai Dang Dau, Nicolas Chopin 

Publication date: 4 January 2024

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: In the context of state-space models, skeleton-based smoothing algorithms rely on a backward sampling step which by default has a $mathcalO(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 rejection sampler with stopping lacks complexity analysis; yet another MCMC-inspired algorithm comes with no stability guarantee. We provide several results that close these gaps. In particular, we prove a novel non-asymptotic 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 framework, a new coupling-based smoothing algorithm applicable to models with intractable transition densities. We elaborate practical recommendations and confirm those with numerical experiments.

Full work available at URL: https://arxiv.org/abs/2207.00976

Recommendations

• Smoothing algorithms for state-space models
• Sequential Monte Carlo smoothing for general state space hidden Markov models
• Coupled conditional backward sampling particle filter
• Backward Nonlinear Smoothing Diffusions
• Monte Carlo Smoothing for Nonlinear Time Series

zbMATH Keywords

sequential Monte Carlosmoothingstate-space model

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05) Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20)

Cites Work

• Pattern recognition and machine learning.
• Filtering via Simulation: Auxiliary Particle Filters
• Particle Markov Chain Monte Carlo Methods
• Title not available (Why is that?)
• Exact and Computationally Efficient Likelihood-Based Estimation for Discretely Observed Diffusion Processes (with Discussion)
• A sequential smoothing algorithm with linear computational cost
• A backward particle interpretation of Feynman-Kac formulae
• An introduction to sequential Monte Carlo
• Efficient particle-based online smoothing in general hidden Markov models: the PaRIS algorithm
• Monte Carlo Smoothing for Nonlinear Time Series
• Sequential Monte Carlo smoothing for general state space hidden Markov models
• Foundations of multidimensional and metric data structures.
• Mean field simulation for Monte Carlo integration
• Sequential quasi Monte Carlo. With discussion and authors' reply
• Particle Filters for Partially Observed Diffusions
• Multilevel Particle Filters
• Genealogies and increasing propagation of chaos for Feynman-Kac and genetic models.
• Stochastic Lotka-Volterra food chains
• On coupling particle filter trajectories
• Smoothing with couplings of conditional particle filters
• Non-asymptotic deviation inequalities for smoothed additive functionals in nonlinear state-space models
• Online Smoothing for Diffusion Processes Observed with Noise
• A pseudo-marginal sequential Monte Carlo online smoothing algorithm

Cited In (1)

• Stochastic filtering of reaction networks partially observed in time snapshots

This page was built for publication: On backward smoothing algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183776)