The reproducing Stein kernel approach for post-hoc corrected sampling

Liam Hodgkinson, Robert Salomone, Fred RoostaarXiv 2020 · DOI · arXiv

TL;DR

This paper introduces a generalized framework for "Stein importance sampling," a method that corrects samples from approximate Markov Chain Monte Carlo (MCMC) algorithms to yield statistically consistent estimators. The key innovation is a universal theory for "reproducing Stein kernels" that allows this correction to be applied to a broader range of MCMC methods, including those that don't perfectly target the desired distribution, and even when using subsampled data.

What Problem Does This Paper Address?

Many real-world problems require sampling from complex probability distributions, often using Markov Chain Monte Carlo (MCMC) methods. However, exact sampling can be computationally intractable. Approximate MCMC methods, like unadjusted MCMC, are faster and can be more efficient in high dimensions, but they often produce samples that are asymptotically biased, meaning they don't perfectly converge to the true target distribution. This lack of theoretical consistency makes statisticians hesitant to adopt them.

The paper addresses this by proposing "Stein importance sampling" as a post-hoc correction. This technique takes samples from an approximate MCMC algorithm and reweights them to create a new, "corrected" distribution that is statistically consistent with the true target. The challenge is to develop a robust theoretical framework for this correction, especially when the underlying MCMC sampler is not perfectly ergodic (i.e., doesn't guarantee convergence to the target distribution) or when dealing with subsampled data.

Methods

The core of the paper lies in developing a universal theory for reproducing Stein kernels and the kernelized Stein discrepancy (KSD).

  • Reproducing Stein Kernels: These are special kernels derived from a target distribution and a "Stein operator" (related to the generator of a Markov process). The authors establish a general method for constructing these kernels on arbitrary Polish spaces, extending existing work on Euclidean spaces and manifolds.
  • Kernelized Stein Discrepancy (KSD): This is a measure of the difference between two probability distributions, computed using the reproducing Stein kernel. The paper shows how KSD can be efficiently computed for empirical distributions (i.e., sets of samples).
  • Stein Importance Sampling: This technique uses the KSD to find optimal weights for the input samples. By minimizing the KSD between the weighted empirical distribution and the target distribution, it effectively "corrects" the samples.
  • Theoretical Guarantees: The paper provides theoretical guarantees for the consistency of Stein importance sampling, even when the original MCMC samples come from a geometrically ergodic Markov chain that is not necessarily π-ergodic (meaning it might not converge to the target distribution). Crucially, they also show that this approach remains consistent when using subsampled data.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and provides numerical experiments on synthetic data (multivariate normal distribution) and a Bayesian logistic regression problem.

Key Insights and Ideas

  • Universality of Stein Kernels: The paper establishes a general framework for constructing reproducing Stein kernels on arbitrary Polish spaces, unifying and extending previous work. This opens the door to applying KSD and Stein importance sampling in a much wider range of settings.
  • Correction Without Perfect Targeting: A significant finding is that Stein importance sampling can yield consistent estimators even if the underlying Markov chain sampler is not perfectly π-ergodic. This is a crucial theoretical justification for using approximate samplers.
  • Subsampling Robustness: The method's ability to retain consistency when data is subsampled is a major practical advantage, especially for large datasets common in modern machine learning.
  • Convergence Determining Property: The paper investigates conditions under which KSD can reliably detect convergence to the target distribution, a property essential for a good discrepancy measure.

Key Results

  • Theorem 1: Establishes sufficient conditions for Stein importance sampling to yield consistent estimators when applied to samples from a V-uniformly ergodic Markov chain, even if it's not perfectly π-ergodic. It also shows consistency under data subsampling.
  • Proposition 1 & 2: Provide general methods for constructing reproducing Stein kernels on general Polish spaces and product spaces, respectively.
  • Numerical Experiments:
    • Demonstrated that Stein importance sampling, when applied to samples from a tamed unadjusted Langevin algorithm (TULA), achieves an O(n⁻¹/²) convergence rate in both MMD and KSD for a 20-dimensional standard normal distribution.
  • Showed that Stein importance sampling, even with subsampled gradients and kernels, can significantly improve the KSD compared to unadjusted samples in binary regression problems.

Limitations and Future Work

  • Computational Complexity: While Stein importance sampling offers theoretical advantages, solving the optimization problem for weights can have cubic complexity in the number of samples. The authors note that for a few thousand samples, this is often manageable.
  • Kernel Choice: The performance of Stein importance sampling is dependent on the choice of the reproducing kernel. While the paper provides general construction methods, selecting an optimal kernel for a specific problem remains an area for further exploration.
  • Extension to More General Kernels: The paper discusses the "canonical Stein kernel" and its properties, but extending the theoretical guarantees to all possible reproducing Stein kernels (especially those not derived from Markov generators) is an ongoing challenge.
  • Practical Implementation: While the theory is strong, practical implementation details for complex, high-dimensional problems might require further investigation. The authors suggest that the framework can be applied to various scenarios, including those involving latent variable models.

Summary updated

Abstract

Stein importance sampling is a widely applicable technique based on kernelized Stein discrepancy, which corrects the output of approximate sampling algorithms by reweighting the empirical distribution of the samples. A general analysis of this technique is conducted for the previously unconsidered setting where samples are obtained via the simulation of a Markov chain, and applies to an arbitrary underlying Polish space. We prove that Stein importance sampling yields consistent estimators for quantities related to a target distribution of interest by using samples obtained from a geometrically ergodic Markov chain with a possibly unknown invariant measure that differs from the desired target. The approach is shown to be valid under conditions that are satisfied for a large number of unadjusted samplers, and is capable of retaining consistency when data subsampling is used. Along the way, a universal theory of reproducing Stein kernels is established, which enables the construction of kernelized Stein discrepancy on general Polish spaces, and provides sufficient conditions for kernels to be convergence-determining on such spaces. These results are of independent interest for the development of future methodology based on kernelized Stein discrepancies.
BibTeX
@misc{hodgkinson2020reproducing,
  author = {Liam Hodgkinson and Robert Salomone and Fred Roosta},
  title = {{The reproducing Stein kernel approach for post-hoc corrected sampling}},
  year = {2020},
  eprint = {2001.09266},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.09266},
}
Figure