论文标题
在向后平滑算法上
On backward smoothing algorithms
论文作者
论文摘要
在状态空间模型的背景下，基于骨架的平滑算法依赖于向后的采样步骤，默认情况下，该步骤具有$ \ Mathcal O（n^2）$复杂性（其中$ n $是粒子的数量）。文献中现有的改进是不令人满意的：我们将表明的一种流行的拒绝抽样可能导致行为不佳的执行时间；另一个带有停止的拒绝采样器缺乏复杂性分析。另一种由MCMC启发的算法没有稳定性保证。我们提供了几种缩小这些差距的结果。特别是，我们证明了一种新颖的非反应稳定性定理，因此可以通过真正的线性复杂性和足够的理论理由进行平滑。我们提出了一个通用框架，该框架将大多数基于骨架的平滑算法团结在一起，并允许在在线和离线环境中同时证明其收敛性和稳定性。此外，我们得出的是该框架的一种特殊情况，这是一种新的基于耦合的平滑算法，适用于具有棘手的过渡密度的模型。我们详细说明了实用建议，并通过数值实验确认那些。
In the context of state-space models, skeleton-based smoothing algorithms rely on a backward sampling step which by default has a $\mathcal 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 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.
