On backward smoothing algorithms

DOI10.1214/23-AOS2324MaRDI QIDQ6183776zbMATH OpenOpenAlexFDO

Authors Hai Dang Dau, Nicolas Chopin

Publication date 4 January 2024

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

Full work available at URL https://arxiv.org/abs/2207.00976, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-5/On-backward-smoothing-algorithms/10.1214/23-AOS2324.full

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)

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.

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

Cites work

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

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)