PaperlayerView exact revision on arXiv

Source-linked AI summary

Measuring Sample Quality with Kernels

Jackson Gorham, Lester Mackey

arXiv:1703.01717v9stat.MLcs.LG

TL;DR

The paper addresses how to assess samples from biased MCMC when standard diagnostics miss asymptotic bias. It develops and analyzes closed-form KSDs using Stein’s method, showing that slowly decaying-tail kernels can determine convergence while some existing KSDs do not. These measures support comparisons and practical sample-quality applications, but their guarantees have scope limits for bounded-score targets and rapidly decaying kernels.

  • Problem

    Standard MCMC diagnostics do not account for asymptotic bias, and previously recommended KSDs can fail to detect non-convergence even for Gaussian targets.

  • Method

    The paper develops weak-convergence theory for closed-form KSDs based on Stein’s method and focuses on the Langevin Stein operator, which requires only the target score function.

  • Results

    The paper proposes convergence-determining KSD alternatives and shows that the IMQ KSD remains bounded away from 0 on an off-target sequence while Gaussian and Matérn KSDs decay to 0.

  • Takeaways & Limitations

    Convergence-determining KSDs can compare biased, exact, and deterministic sample sequences and are easily computable and parallelizable.

  • Takeaways & Limitations

    Rapidly decaying kernels can ignore excess tail mass, and no C0-kernel KSD dominates weak convergence when the target has a bounded score function.

Abstract

from arXiv · show

Approximate Markov chain Monte Carlo (MCMC) offers the promise of more rapid sampling at the cost of more biased inference. Since standard MCMC diagnostics fail to detect these biases, researchers have developed computable Stein discrepancy measures that provably determine the convergence of a sample to its target distribution. This approach was recently combined with the theory of reproducing kernels to define a closed-form kernel Stein discrepancy (KSD) computable by summing kernel evaluations across pairs of sample points. We develop a theory of weak convergence for KSDs based on Stein's method, demonstrate that commonly used KSDs fail to detect non-convergence even for Gaussian targets, and show that kernels with slowly decaying tails provably determine convergence for a large class of target distributions. The resulting convergence-determining KSDs are suitable for comparing biased, exact, and deterministic sample sequences and simpler to compute and parallelize than alternative Stein discrepancies. We use our tools to compare biased samplers, select sampler hyperparameters, and improve upon existing KSD approaches to one-sample hypothesis testing and sample quality improvement.

1. Introduction

The paper motivates practical sample-quality measures for biased MCMC and develops kernel Stein discrepancies to assess convergence without explicit integration under the target.

  • The framework targets intractable expectations under a target distribution and uses the target score function in its practical Stein-operator construction.
  • Biased MCMC procedures trade asymptotic correctness for increased sampling speed, while standard diagnostics do not account for asymptotic bias.
  • Kernel Stein discrepancies provide closed-form sample-quality measures whose computation requires no linear-program solver and can be easily parallelized.
  • Previously recommended KSDs can fail to detect non-convergence in dimensions d ≥3, motivating convergence-determining alternatives.
  • The paper develops weak-convergence theory for KSDs and applies the resulting measures to hyperparameter selection, sampler selection, one-sample hypothesis testing, and sample-quality improvement.

2. Quality measures for samples

The paper evaluates weighted samples by measuring expectation-approximation error over test-function classes, using Stein’s method to avoid direct integration under the target.

  • The framework assumes a continuously differentiable density on all of R^d and an evaluable score function, while direct integration is infeasible for many functions of interest.
  • Weighted samples may arise from Markov chains or be generated deterministically, with no assumptions about their origins.
  • The desired quality measure should identify convergence, detect non-convergence, and be efficiently computable when comparing samples targeting P.
  • Discrepancies quantify the maximum expectation error over a class of test functions.
  • Choosing test functions whose expectations under P are zero eliminates the need for explicit integration, following Stein’s method for characterizing distributional convergence.

3. Stein’s method with kernels

The paper develops kernel Stein discrepancies by combining Stein’s method with reproducing kernel Hilbert spaces, yielding computable measures whose convergence properties depend on kernel tails and target assumptions.

  • Stein’s method: Stein’s method constructs a convergence diagnostic by selecting an operator, relating its discrepancy to a weak-convergence-dominating IPM, and proving the reverse vanishing bound.The resulting framework supports both convergence guarantees and practical sample-quality measurement.
  • Selecting a Stein operator and a Stein set: The Langevin Stein operator depends on the target only through its score function, so its computation does not require the target-density normalizing constant.The paper focuses on this operator while noting compatibility with diffusion Stein operators.
  • Selecting a Stein operator and a Stein set: KSDs restrict vector-valued test functions to RKHS components whose norm vector lies in the dual-norm unit ball.This reproducing-kernel construction defines the kernel Stein set used by the discrepancy.
  • Kernel Stein discrepancies: KSDs admit a closed-form solution from Stein kernels, recovering prior KSDs under the Euclidean norm and enabling pairwise computation that is easily parallelized.The closed form avoids linear-program solvers; the discrete-measure computation sums Stein-kernel evaluations over sample pairs and coordinates.
  • Convergence properties: In dimensions d ≥3, light-tailed kernels can yield KSDs approaching zero for non-convergent sequences, including Gaussian targets and common Gaussian, Matérn, and compactly supported kernels.The failure arises because rapidly decaying kernels may ignore mass escaping into increasingly diffuse tails.
  • Convergence properties: Slowly decaying IMQ kernels with exponent β > −1 enforce uniform tightness and determine weak convergence for distantly dissipative targets under the stated smoothness conditions.The paper also establishes weak-convergence detection for uniformly tight sequences and gives an upper bound when Wasserstein distance vanishes.

4. Experiments

Experiments show that convergence-determining IMQ KSDs identify off-target samples, compare biased samplers and hyperparameters, and improve testing and sample optimization while remaining computationally practical.

  • 4.1. Comparing discrepancies: The IMQ KSD decays at an n^-0.51 rate for target samples but remains bounded away from zero for samples from one mixture component.This behavior closely matches the Wasserstein distance and graph Stein discrepancy.
  • 4.1. Comparing discrepancies: KSD computation is 10 to 1000 times faster than graph Stein discrepancy in d = 4 and is straightforwardly parallelized without a linear program solver.The methods have nearly identical runtimes when d = 1.
  • 4.2. KSD failure and alternatives: Gaussian and Matérn KSDs decay to 0 on an off-target sequence for Gaussian targets, whereas the IMQ KSD remains bounded away from 0.The failure becomes more pronounced as dimension increases; the constructed sequence applies whenever d ≥ 3.
  • 4.3. Selecting sampler hyperparameters: Across 50 approximate slice-sampler chains, IMQ KSD selects ϵ = 10^-2 while ESS selects ϵ = 10^-1, and the KSD-selected sample best resembles the posterior target.The ESS-selected chain is significantly overdispersed, while ϵ = 0 provides minimal coverage because of its small sample size; the longest KSD computation took 0.16s using 4 cores.
  • 4.4. Selecting samplers: KSD evaluation finds that SGFS-d’s moderate speed-up is outweighed by a significant loss in inferential accuracy relative to SGFS-f.Per-sample times were 0.0017s for SGFS-d and 0.0019s for SGFS-f, while the longest KSD computation took 400s using 16 cores.
  • 4.5. Beyond sample quality comparison: The IMQ KSD improves one-sample normality testing by avoiding power degradation across the evaluated dimensions and improves mean estimates over the standard Gaussian kernel.The sample-quality experiments also apply IMQ KSD to optimized samples and Bayesian logistic-regression sampler comparisons.

5. Related and future work

The paper situates KSDs within Stein-discrepancy research, identifies limits on convergence guarantees, and outlines extensions to other Stein-based applications and target distributions.

  • Universal or ISPD kernels can make KSD zero only at the target, but this does not ensure weak convergence.Gaussian and Matérn kernels can have KSDs tending to zero along non-convergent sequences.
  • On compact domains, existing results provide conditions under which a KSD dominates weak convergence.
  • The recommended kernels could be incorporated into Monte Carlo control functionals, variational inference, and Stein generative adversarial networks.
  • Future work targets stochastic, low-rank, and sparse approximations that scale KSDs better while preserving weak-convergence guarantees.
  • For bounded score functions, no KSD with a C0 kernel dominates weak convergence.
  • Diffusion Stein operators may yield convergence-determining diffusion KSDs beyond the paper’s target class, with extensions also covering convex supports.

B. Proof of Proposition 1: Zero mean test functions

The proof establishes that Stein test functions have zero expectation under the target by combining RKHS regularity, integrability, and expectation–inner-product exchange.

  • RKHS smoothness and bounded kernel derivatives imply finite M0(gj) and M1(gj) for every component.
  • Each coordinate Stein operator is T^j_P g0(x) = ∇xj g0(x) + bj(x)g0(x).
  • The canonical RKHS feature map Ψk(x) = k(x, ·) supports the operator representation used in the proof.
  • The representation and µ-integrability assumption make T^j_P Ψk Bochner µ-integrable.
  • Exchanging expectation with the RKHS inner product and applying the representation and Fenchel–Young inequality yields the zero-mean result.

D. Proof of Proposition 3: Stein set equivalence

The proof shows that KSDs defined using different vector norms are equivalent up to dimension- and norm-dependent constants.

  • For some vector w, the KSDs under a generic norm and the Euclidean norm equal ∥w∥ and ∥w∥2, respectively.Norm equivalence gives constants cd, c′d > 0 depending only on d and the chosen norm.

E. Proof of Theorem 5: Univariate KSD detects non-convergence

The proof constructs a weak-convergence-dominating IPM and bounds it using KSD, with Stein solutions, tilting, smoothing, and Fourier control providing the required approximation.

  • Step 1: Reference IPM: An ISPD reference kernel defines an RKHS test-function class whose IPM dominates weak convergence.
  • Step 1: Reference IPM: The proof obtains rates O(1/log(1/S)) for Gaussian and inverse multiquadric kernels and O(S^(1/(v+1/2))) for Matérn kernels with v > 1.
  • Step 1: Reference IPM: If the KSD tends to zero, the reference IPM tends to zero, implying weak convergence to P.
  • Step 2: Stein solution: The proof uniformly bounds test functions and their gradients over the reference class using a tilted kernel construction.
  • Step 2: Stein solution: A tilted distribution with density proportional to p(x)/Ξ(x) preserves distant dissipativity under the stated bounds.
  • Step 2: Stein solution: The resulting Stein solution satisfies gh(x) ≤ MP/(1 + ∥x∥2)^(1/2), giving ∥gh∥L2 ≤ MP√π when d = 1.
  • Step 3: Stein approximation: Smoothing constructs finite-RKHS-norm functions whose Stein operators uniformly approximate the target Stein function.
  • Step 3: Stein approximation: The approximation error is controlled by the smoothing scale and Lipschitz constants, after which taking a supremum over h yields the theorem.

F. Proof of Theorem 6: KSD fails with light kernel tails

The proof constructs point sequences whose KSD tends to zero despite escaping probability-mass control, showing that light-tailed kernels can miss non-convergence. For Gaussian targets, the sequence is not uniformly tight and therefore converges to no probability measure.

  • Construction: The construction places n distinct points in a ball of radius r_n while enforcing pairwise separation greater than Δ_n.Here Δ_n=max(1,γ^-1(1/n)) and r_n=Δ_n n^1/d.
  • Gaussian target: For the Gaussian target P=N(0,I_d), the Stein kernel term combines inner products with kernel values and derivatives.The score is b(x)=−x, yielding the displayed expression for k_0(x,y).
  • Discrepancy bound: The resulting Stein discrepancy is bounded using the kernel and derivative decay controlled by γ, together with the chosen separation and radius scales.The proof applies triangle and Cauchy–Schwarz bounds to diagonal and off-diagonal contributions.
  • Discrepancy bound: S(Q_n,T_P,G_k)→0 as n→∞ when γ(r)=o(r^-α), because γ^-1(1/n)=o(n^(1/2−1/d)).This rate makes the constructed sequence appear convergent under the KSD.
  • Failure of convergence detection: The sequence (Q_n) is not uniformly tight and hence converges to no probability measure.Thus the KSD fails to detect non-convergence for this light-tailed-kernel construction.

G. Proof of Theorem 7: KSD detects tight non-convergence

The proof bounds the bounded Lipschitz distance by tightness, Fourier-transform decay, and KSD, using smoothing and truncation of Stein solutions. Under uniform tightness and vanishing KSD, this yields weak convergence.

  • Bounded Lipschitz control: The tightness rate R(μ,ε) quantifies the radius needed to contain all but ε probability mass.The theorem uses this rate as one of the controlling terms in the bounded Lipschitz bound.
  • Bounded Lipschitz control: Theorem 13 bounds d_BL(μ,P) using R(μ,ε), generalized Fourier-transform decay F, and S(μ,T_P,G_k).The bound also depends on target-specific constants and tuning parameters ρ, ε, and δ.
  • Convergence implication: For uniformly tight (μ_m), S(μ_m,T_P,G_k)→0 implies d_BL(μ_m,P)→0 and therefore μ_m⇒P.Uniform tightness keeps the tightness-rate term bounded, while non-vanishing Fourier transforms keep F finite.
  • Stein-solution approximation: The proof smooths Stein solutions by Gaussian convolution, preserving a uniform sup-norm bound while making the functions sufficiently regular.The smoothed function is g_ρ(x)=E[g(x−ρU)] for U∼N(0,I_d).
  • Stein-solution approximation: It then truncates the smoothed solution with a compactly supported cutoff that equals one on K and vanishes outside K_2δ.This produces an L2-admissible approximation while controlling the Stein-operator error inside and outside K.
  • Stein-solution approximation: Approximating the truncated function in the kernel Stein set yields a uniform Stein-output error bounded by ε on K and controlled outside K.Uniform tightness makes the outside-K contribution small in expectation.

H. Proof of Theorem 8: IMQ KSD detects non-convergence

The proof shows that inverse multiquadric kernels prevent vanishing KSD sequences from escaping to infinity, then combines tightness with the bounded Lipschitz bound. Consequently, vanishing IMQ KSD implies weak convergence.

  • Tightness: If lim sup_m S(μ_m,T_P,G_k)<∞, then (μ_m) is uniformly tight.This is the key property that rules out the escaping-point failure exhibited for light-tailed kernels.
  • Fourier control: The IMQ Fourier transform is controlled through modified Bessel-function bounds, making the Fourier-decay term finite and enabling the Theorem 13 bound.The proof uses monotonicity in frequency norm and asymptotic decay of the Bessel function.
  • Weak convergence: With IMQ-induced tightness and the bounded Lipschitz lower-bound argument, S(μ_m,T_P,G_k)→0 implies d_BL(μ_m,P)→0 and hence μ_m⇒P.The proof obtains the advertised decay rate by selecting ε and ρ as functions of the KSD.
  • Coercive Stein function: Generalized multiquadric Stein sets contain a function whose Stein output is uniformly bounded below and grows coercively at infinity.The growth rate is proportional to ∥x∥_2^(2α) under the stated parameter restrictions.
  • Tightness: Coercive Stein outputs yield a tightness-rate bound through Markov’s inequality, converting bounded KSD into uniform tightness.The argument bounds μ(∥X∥_2≥r_ε) by ε for sufficiently small ε.

I. Proof of Proposition 9: KSD detects convergence

The proof establishes a uniform upper bound on Stein outputs for the kernel Stein set by combining regularity assumptions with a general Stein-output inequality. This controls the discrepancy through Wasserstein distance.

  • Stein-output bound: The Stein-output upper bound assumes a Lipschitz score with finite target second moment and uniformly bounded function derivatives through order two.Under these assumptions, Stein outputs can be bounded in terms of Wasserstein distance.
  • Stein-output bound: The Wasserstein distance d_W(μ,P) is defined as the infimum of E[∥X−Z∥_2] over couplings with X∼μ and Z∼P.This coupling formulation enters the final Stein-output inequality.
  • Stein-output bound: Stein’s identity gives E_P[(T_Pg)(Z)]=0, allowing the output difference to be controlled using triangle, Jensen, and Fenchel–Young inequalities.The proof then takes the infimum over all admissible couplings.
  • Kernel regularity: Kernel derivative bounds imply that every g in G_k has uniformly bounded M_0(g), M_1(g), and M_2(g), with a common finite constant λ_k.Applying the Stein-output lemma yields the proposition’s advertised result.

J. Proof of Theorem 10: KSD fails for bounded scores

The proof constructs a sequence whose KSD tends to zero while the corresponding probability measures are not uniformly tight and therefore do not converge to the target distribution.

  • S(Qn, TP, Gk) → 0 as n → ∞ when M0(b) is finite.The construction uses points xi with pairwise Euclidean distances at least n.
  • The kernel Stein kernel k0 combines score products, score-gradient terms, and mixed second-derivative terms.
  • As pairwise distances grow, the kernel decay rate satisfies γ(r) → 0, driving the relevant averaged kernel terms toward zero.
  • The proof bounds |k0(xi, xi′)| by the sum of the absolute values of these four component terms.
  • Despite the vanishing KSD, the constructed sequence is not uniformly tight and hence does not converge to P.
Loading 1703.01717v9…