Non-asymptotic deviation inequalities for smoothed additive functionals in non-linear state-space models

Cyrille Dubarry, Sylvain Le Corff

Abstract

The approximation of fixed-interval smoothing distributions is a key issue in inference for general state-space hidden Markov models (HMM). This contribution establishes non-asymptotic bounds for the Forward Filtering Backward Smoothing (FFBS) and the Forward Filtering Backward Simulation (FFBSi) estimators of fixed-interval smoothing functionals. We show that the rate of convergence of the $L_q$-mean errors of both methods depends on the number of observations $T$ and the number of particles $N$ only through the ratio $T/N$ for additive functionals. In the case of the FFBS, this improves recent results providing bounds depending on $T$ and the square root of $N$.

Introduction

In state-space modeling, particularly within the framework of Hidden Markov Models (HMMs), researchers often seek to estimate a sequence of hidden states based on a series of noisy observations. While "filtering" focuses on estimating the current state given past data, "smoothing" involves estimating the entire trajectory of hidden states over a fixed time interval $[0, T]$ using all available information.

For non-linear and non-Gaussian models, exact smoothing is analytically intractable. Practitioners rely on Sequential Monte Carlo (SMC) methods, or particle filters, which approximate probability distributions using a set of $N$ random samples (particles). However, a persistent challenge in SMC research has been understanding the relationship between the observation duration $T$ and the number of particles $N$ required to maintain accuracy. This paper provides a rigorous theoretical framework that significantly improves the known error bounds for two primary smoothing algorithms.

The Problem: Path Degeneracy and Scaling

A major hurdle in particle smoothing is "path degeneracy." In standard path-space SMC methods, the genealogical history of particles tends to collapse over time, meaning that for early time steps, almost all current particles share a single common ancestor. This leads to a massive loss of diversity and high variance in estimates as $T$ increases.

Previous theoretical work suggested that for the Forward Filtering Backward Smoothing (FFBS) algorithm, the estimation error might grow as $T/\sqrt{N}$. This implies that to maintain a constant error level as the observation window grows, the number of particles would need to increase quadratically ($N \propto T^2$), which is computationally prohibitive for long-duration datasets. This research investigates whether a more favorable scaling is possible.

Methodology: FFBS and FFBSi

The authors analyze two sophisticated smoothing techniques designed to mitigate degeneracy:

  1. Forward Filtering Backward Smoothing (FFBS): This is a two-pass algorithm. It first performs a standard forward pass to generate filtering distributions. In the backward pass, it reweights these particles to incorporate information from future observations, effectively "correcting" the trajectory estimates.
  2. Forward Filtering Backward Simulation (FFBSi): Similar to FFBS, this method generates entire smoothed trajectories by sampling from the forward particles in a backward fashion. It is often preferred in practice for its ability to produce distinct sample paths.

To derive the new bounds, the authors decompose the smoothing error into a martingale difference sequence. By applying advanced probabilistic tools—specifically Burkholder’s inequality and Azuma-Hoeffding inequalities—they establish non-asymptotic bounds. Unlike asymptotic results that only hold as $N$ approaches infinity, these non-asymptotic guarantees provide concrete reliability metrics for the finite particle counts used in real-world applications.

Key Theoretical Insights

The $T/N$ Convergence Rate

The central finding of the paper is that for additive functionals, the $L_q$-mean error of both FFBS and FFBSi depends on $T$ and $N$ only through the ratio $T/N$. This is a significant improvement over the $T/\sqrt{N}$ bound previously associated with FFBS. It implies that the error scales linearly with time; if the observation window doubles, one only needs to double the number of particles to maintain the same level of precision.

Exponential Deviation Inequalities

Beyond mean error, the authors prove an exponential deviation inequality. This provides a "confidence guarantee": the probability that the estimation error exceeds a specific threshold $\epsilon$ decreases exponentially as the number of particles $N$ increases relative to $T$. This result is vital for safety-critical applications where worst-case error bounds are more important than average performance.

The Role of Strong Mixing

The proofs rely on the assumption that the HMM is "strongly mixing." This means the system essentially "forgets" its initial conditions at a sufficiently fast rate. Under these conditions, the smoothing error can be treated as a sum of nearly independent components, which prevents the variance from exploding quadratically and allows for the $T/N$ scaling.

Empirical Validation

The theoretical findings were tested using two primary benchmarks:

  • Linear Gaussian Model (LGM): Used as a baseline because the exact solution (the Kalman Filter) is known, allowing the authors to verify that the particle approximations converge to the true values at the predicted rates.
  • Stochastic Volatility Model (SVM): A non-linear model used in financial econometrics. The simulations confirmed that FFBSi significantly outperforms traditional path-space SMC methods, exhibiting much lower empirical variance for the same computational budget.

Conclusion and Future Work

This work provides a much-needed theoretical justification for the efficiency of FFBS and FFBSi. By proving that the error scales with $T/N$, the authors demonstrate that these algorithms are far more robust for long-term smoothing than previously thought.

However, the reliance on "strong mixing" remains a limitation, as some high-dimensional or low-noise systems may not satisfy these conditions. Future research may focus on relaxing these assumptions or extending these non-asymptotic bounds to the problem of parameter estimation (Maximum Likelihood Estimation) in non-linear state-space models.

Summary updated

Abstract

The approximation of fixed-interval smoothing distributions is a key issue in inference for general state-space hidden Markov models (HMM). This contribution establishes non-asymptotic bounds for the Forward Filtering Backward Smoothing (FFBS) and the Forward Filtering Backward Simulation (FFBSi) estimators of fixed-interval smoothing functionals. We show that the rate of convergence of the Lq-mean errors of both methods depends on the number of observations T and the number of particles N only through the ratio T/N for additive functionals. In the case of the FFBS, this improves recent results providing bounds depending on T and the square root of N.
BibTeX
@inproceedings{dubarry2013non,
  author = {Cyrille Dubarry and Sylvain Le Corff},
  title = {{Non-asymptotic deviation inequalities for smoothed additive functionals in non-linear state-space models}},
  booktitle = {Bernoulli},
  year = {2013},
  doi = {10.3150/12-bej450},
}
Figure