Optimized Auxiliary Particle Filters: adapting mixture proposals via convex optimization

Nicola Branchini, Víctor Elvira

TL;DR

This paper introduces Optimized Auxiliary Particle Filters (OAPF), a novel framework that improves Bayesian inference in dynamic systems by optimizing the proposal distribution used in particle filters. OAPF achieves this by formulating the selection of mixture proposal weights as a convex optimization problem, leading to more accurate estimates and reduced variance compared to existing methods.

What Problem Does This Paper Address?

State-space models (SSMs) are crucial for understanding complex dynamical systems, and Particle Filters (PFs) are the go-to method for Bayesian inference in these models. However, standard PFs can suffer from "weight degeneracy," where a few particles get disproportionately high weights, leading to poor approximations. Auxiliary Particle Filters (APFs) were developed to mitigate this by using an auxiliary variable to improve inference. While APFs offer improvements, their original formulation and subsequent adaptations still have limitations, particularly in complex, non-linear, and non-Gaussian models. This paper addresses the challenge of creating more robust and accurate particle filters by proposing a method to optimize the proposal distribution itself, aiming to better match the true posterior and thus reduce the variance of particle weights.

Methods

The core innovation of OAPF lies in its interpretation of APF's auxiliary variables as weights for a mixture proposal distribution. Instead of relying on fixed or heuristic methods for choosing these weights, OAPF formulates this selection as a convex optimization problem. This allows the algorithm to adaptively learn the optimal mixture weights at each time step, aiming to approximate the filtering posterior. Specifically, the authors propose:

  • Mixture Proposal: A flexible proposal distribution is constructed as a mixture of kernels.
  • Convex Optimization: The mixture weights are optimized by minimizing the discrepancy between the proposal and the target posterior at a set of evaluation points. This is framed as a non-negative least squares (NNLS) problem, which is convex and thus efficiently solvable.
  • Weighting Scheme: A generalized weighting scheme is introduced, which is proven to be unbiased and consistent, extending previous APF results.

This approach allows for a flexible choice of the number of mixture components, independent of the number of particles, and avoids the need for black-box, non-convex optimization methods often used in related fields.

Datasets

The paper evaluates OAPF on several standard and challenging dynamical models:

  • Toy Example: Used to visually demonstrate the OAPF proposal's ability to match unimodal and multimodal posteriors.
  • Linear Dynamical Model: A well-established model, often used for benchmarking PFs, allowing for comparison with Kalman Filters and the Fully Adapted APF (FA-APF).
  • Stochastic Lorenz 63 Model: A chaotic system known for its sensitivity to initial conditions and parameters, representing a non-linear, non-Gaussian challenge.
  • Stochastic Volatility Model: A multivariate model commonly used in econometrics and for evaluating APFs.

No new datasets were introduced; the focus was on applying OAPF to existing benchmark models.

Key Insights and Ideas

  • Convex Optimization for Proposals: Framing the selection of mixture proposal weights as a convex optimization problem is a significant departure. It offers a principled and efficient way to adapt the proposal to the target posterior, directly addressing the core challenge of variance reduction in particle filters.
  • Flexibility in Kernel Choice: The OAPF framework allows for a flexible choice of the number of mixture kernels (K), decoupling it from the number of particles (M). This is a key advantage over some existing methods where K is often tied to M.
  • Theoretical Guarantees: The paper provides theoretical proofs for the unbiasedness and consistency of the OAPF estimator, offering strong theoretical backing for its performance.
  • Generalization of APF: OAPF can be seen as a generalization of existing APF methods, encompassing them as special cases while offering improved performance.
  • Sparsity Advantage: The optimization process can lead to sparse solutions for the mixture weights, potentially reducing computational complexity.

Key Results

The OAPF framework demonstrated significant improvements across various experiments:

  • Toy Example: OAPF proposals were shown to be much closer to the true posteriors, with substantially lower $\chi^2$-divergence compared to BPF, APF, and IAPF.
  • Linear Dynamical Model: OAPF achieved superior performance (lower Normalized Mean Squared Error for posterior mean) compared to BPF, APF, IAPF, and FA-APF, especially with a small number of kernels (K=E=5), leading to significant computational savings.
  • Stochastic Lorenz 63 Model: OAPF showed improved performance in terms of Effective Sample Size (ESS), a proxy for weight variance, compared to other methods.
  • Stochastic Volatility Model: OAPF consistently achieved higher ESS values across different dimensions, indicating better weight quality.
  • Computational Complexity: Despite its advanced optimization, OAPF achieved comparable or better results with similar computational complexity to state-of-the-art methods.

Limitations and Future Work

  • Computational Cost of Optimization: While the optimization is convex, it still adds a computational overhead at each time step. The paper notes that this can be accelerated by implementing standard optimization techniques.
  • Choice of Evaluation Points: The paper suggests a simple strategy for selecting evaluation points (centers of kernels), but acknowledges that exploring more sophisticated strategies for selecting these points could further improve performance.
  • Formal Analysis of Sparsity: The paper mentions the sparsity observed in the optimization solutions and suggests that further work could develop a formal analysis to explain this behavior.
  • Generalization of Kernels: While the paper uses transition kernels as proposal kernels, it notes that other choices are possible and could be explored.
  • Further Methodological Advances: The authors believe the flexibility and theoretical guarantees of OAPF pave the way for new methodological advances within the framework.

Summary updated

Abstract

Auxiliary particle filters (APFs) are a class of sequential Monte Carlo (SMC) methods for Bayesian inference in state-space models. In their original derivation, APFs operate in an extended state space using an auxiliary variable to improve inference. In this work, we propose optimized auxiliary particle filters, a framework where the traditional APF auxiliary variables are interpreted as weights in a importance sampling mixture proposal. Under this interpretation, we devise a mechanism for proposing the mixture weights that is inspired by recent advances in multiple and adaptive importance sampling. In particular, we propose to select the mixture weights by formulating a convex optimization problem, with the aim of approximating the filtering posterior at each timestep. Further, we propose a weighting scheme that generalizes previous results on the APF (Pitt et al. 2012), proving unbiasedness and consistency of our estimators. Our framework demonstrates significantly improved estimates on a range of metrics compared to state-of-the-art particle filters at similar computational complexity in challenging and widely used dynamical models.
BibTeX
@inproceedings{branchini2021optimized,
  author = {Nicola Branchini and Víctor Elvira},
  title = {{Optimized Auxiliary Particle Filters: adapting mixture proposals via convex optimization}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=TRfdkdFjJF-},
}
Figure