Nearly Consistent Finite Particle Estimates in Streaming Importance Sampling

Alec Koppel, Amrit Singh Bedi, Brian M. Sadler, Víctor ElviraIEEE TSP 2021 · DOI · OpenReview

TL;DR

This paper introduces a novel method for "streaming importance sampling" that significantly reduces the memory footprint of Bayesian inference. By embedding particle estimates in a Reproducing Kernel Hilbert Space (RKHS) and using a greedy projection technique, the algorithm maintains near-statistical consistency while keeping the number of particles fixed, overcoming a key limitation of traditional methods.

What Problem Does This Paper Address?

Bayesian inference is crucial for understanding complex systems by estimating unknown variables from data. When the underlying probability distributions are intractable, Monte Carlo (MC) methods, particularly Importance Sampling (IS), are used. IS approximates these distributions with weighted samples (particles). While IS is asymptotically consistent (meaning it gets more accurate as you use more particles), it requires an infinite number of particles for perfect accuracy, which is computationally infeasible. This leads to the "curse of dimensionality," where the memory and computational cost grow exponentially with the complexity of the problem. The paper addresses the challenge of achieving accurate Bayesian inference with a finite and manageable number of particles, especially in an online setting where data arrives sequentially.

Methods

The core innovation lies in a two-step process applied online:

  1. Kernel Mean Embedding (KME): The algorithm first embeds the current estimate of the posterior distribution into a Reproducing Kernel Hilbert Space (RKHS). This is done by representing the distribution as a "kernel mean embedding," which allows for mathematical operations in a high-dimensional feature space that correspond to operations on probability distributions. This embedding is parameterized by the particles and their importance weights.
  2. Greedy Subspace Projection (MMD-OMP): The embedded distribution is then projected onto a lower-dimensional subspace. This subspace is defined by a dictionary of selected particles. The selection process uses a greedy approach, specifically a variant of Orthogonal Matching Pursuit (OMP) guided by the Maximum Mean Discrepancy (MMD). MMD is an integral probability metric that measures the distance between two distributions. The algorithm greedily selects particles that best represent the embedded distribution, effectively compressing the representation while minimizing the discrepancy. This process is repeated for each new incoming particle.

This approach allows the algorithm to maintain a fixed-size dictionary of particles (and their associated weights) over time, rather than accumulating all past particles.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated for specific problems to demonstrate the algorithm's performance. These include:

  • A problem involving estimating the expected value of a function with a known target and proposal distribution.
  • A problem simulating indirect importance sampling using a non-linear observation model.
  • A sensor network localization experiment, where the goal is to estimate the location of a static target in 2D space based on range measurements.

Key Insights and Ideas

  • RKHS as a Bridge: Embedding distributions into RKHS provides a powerful mathematical framework to perform operations (like projection and distance calculation) that are intractable in the original measure space.
  • MMD for Greedy Selection: Using Maximum Mean Discrepancy as a metric for greedy particle selection is an effective way to identify the most statistically significant particles for representation.
  • Tunable Trade-off: The compression parameter (ε) in the MMD-OMP algorithm allows for a direct, tunable trade-off between the accuracy of the integral estimate (consistency) and the memory required to store the particle representation.
  • Near-Consistency with Finite Memory: The most significant insight is that it's possible to achieve nearly consistent estimates with a finite and bounded memory, which is a major departure from traditional IS that requires infinite memory for asymptotic consistency.

Key Results

  • Substantial Memory Reduction: Experiments show that the proposed Compressed Kernelized IS (CKIS) algorithm achieves substantial reductions in representational complexity (model order) compared to standard IS, often by orders of magnitude. For instance, in one experiment, the model order stabilized around 56, while the uncompressed IS algorithm's memory grew linearly with the number of iterations.
  • Comparable Accuracy: Despite the significant memory reduction, the CKIS algorithm maintains comparable accuracy to the uncompressed IS. The integral estimation error was shown to be on the order of 10⁻³, with the compressed estimates being very close to the dense ones.
  • Theoretical Guarantees: The paper provides theoretical results establishing that the algorithm's asymptotic bias is determined by the compression parameter and kernel bandwidth, offering a tunable approach to balancing consistency and memory. Theorem 1 and 2 provide bounds on the error and model order, respectively.

Limitations and Future Work

  • "Nearly Consistent": The algorithm is described as "nearly consistent," meaning it converges to a neighborhood of the true value, not necessarily the exact value. The size of this neighborhood is controlled by the compression parameter.
  • Choice of Kernel: The performance and theoretical guarantees depend on the choice of the kernel function and its bandwidth.
  • Computational Cost of MMD-OMP: While MMD-OMP reduces memory, the computational cost of the projection step itself can still be significant, especially for very high-dimensional feature spaces or large dictionaries.
  • Future Work: The authors suggest that this approach can be extended to other memory-intensive Monte Carlo methods and applied to complex nonlinear signal processing problems like localization, which have been challenging due to their computational burden. They also mention that adaptive algorithms could be used for more general scenarios.

Summary updated

Abstract

In Bayesian inference, we seek to compute information about random variables such as moments or quantiles on the basis of available data and prior information. When the distribution of those random variables is intractable, Monte Carlo (MC) sampling is usually required. Importance sampling is a standard MC tool that approximates this unavailable distribution with a set of weighted samples. This procedure is asymptotically consistent as the number of MC samples (particles) goes to infinity. However, retaining infinitely many particles is infeasible. Thus, we propose a way to only keep a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">finite representative subset</i> of particles and their augmented importance weights that is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">nearly consistent</i> , i.e., they converge to a close neighborhood of their population ground truth in the large sample limit. To do so in an online manner, we (1) embed the posterior density estimate in a reproducing kernel Hilbert space (RKHS) through its kernel mean embedding; and (2) sequentially project this RKHS element onto a lower-dimensional subspace in RKHS using the maximum mean discrepancy, an integral probability metric. Theoretically, we establish that this scheme results in a bias determined by a compression parameter, which yields a tunable tradeoff between consistency and memory. In experiments, we observe the compressed estimates achieve comparable performance to the dense ones with substantial reductions in representational complexity.
BibTeX
@article{koppel2021nearly,
  author = {Alec Koppel and Amrit Singh Bedi and Brian M. Sadler and Víctor Elvira},
  title = {{Nearly Consistent Finite Particle Estimates in Streaming Importance Sampling}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  doi = {10.1109/tsp.2021.3120512},
}
Figure