Source-linked AI summary
Measuring Sample Quality with Stein's Method
Jackson Gorham, Lester Mackey
TL;DR
Biased MCMC improves speed by trading asymptotic exactness for potentially lower variance, exposing a gap in standard sample-quality diagnostics. The paper introduces a computable Stein discrepancy based on target functionals with known expectations, establishes convergence links to Wasserstein distance, and applies it to sampler selection and bias-variance assessment. Its scope includes specific target regularity conditions and assumptions such as known target density structure and, in one setup, convex support.
Problem
Standard sample-quality measures do not account for asymptotic bias in faster, biased MCMC procedures, complicating sampler and parameter selection.
Method
The paper develops a Stein-based sample-quality measure that optimizes over an infinite class of target-centered functionals and computes the resulting discrepancy efficiently.
Results
For strongly log-concave targets with bounded continuous third and fourth derivatives, Stein discrepancy convergence to zero implies Wasserstein convergence.
Takeaways & Limitations
The discrepancy supports comparisons of exact, biased, and deterministic sample sequences and applications including hyperparameter selection and posterior bias-variance tradeoffs.
Takeaways & Limitations
The main convergence theorem requires strong log-concavity with bounded continuous third and fourth derivatives, although those conditions are not necessary for every lower bound.
Abstract
from arXiv · showhide
To improve the efficiency of Monte Carlo estimation, practitioners are turning to biased Markov chain Monte Carlo procedures that trade off asymptotic exactness for computational speed. The reasoning is sound: a reduction in variance due to more rapid sampling can outweigh the bias introduced. However, the inexactness creates new challenges for sampler and parameter selection, since standard measures of sample quality like effective sample size do not account for asymptotic bias. To address these challenges, we introduce a new computable quality measure based on Stein's method that quantifies the maximum discrepancy between sample and target expectations over a large class of test functions. We use our tool to compare exact, biased, and deterministic sample sequences and illustrate applications to hyperparameter selection, convergence rate assessment, and quantifying bias-variance tradeoffs in posterior inference.
1 Introduction
Biased MCMC can trade asymptotic correctness for faster sampling, but standard diagnostics do not account for the resulting bias. The paper develops a computable Stein-based discrepancy for comparing exact, biased, and deterministic samples and establishes convergence properties supporting its use.
- 1 Introduction: Biased MCMC procedures can reduce Monte Carlo variance through faster sampling, but standard quality measures presume eventual convergence and therefore ignore asymptotic bias.This creates challenges for selecting samplers and their parameters.
- 1 Introduction: The proposed quality measure compares sample and target expectations over a test-function class whose target expectations are known through Stein’s method.This avoids generic integration under the target distribution.
- 1 Introduction: The Stein discrepancy is computed by solving a linear program and is designed to compare asymptotically exact, asymptotically biased, and deterministic sample sequences.The paper also develops an efficient geometric-spanner implementation.
- 1 Introduction: The Stein operator depends on the target only through the derivative of its log density, so its normalizing constant need not be known.The operator is therefore computable when the target density is known only up to normalization.
- 1 Introduction: For strongly log-concave densities with bounded continuous third and fourth derivatives, Stein discrepancy convergence to zero implies Wasserstein convergence.The stated class includes Bayesian logistic regression posteriors under Gaussian priors.
- 1 Introduction: The classical Stein discrepancy converges to zero when sample measures converge in mean square and their target log-density gradients converge in mean.This provides a sufficient condition for convergence of the quality measure.
4 Computing Stein Discrepancies
The paper makes Stein discrepancies computationally tractable by replacing infinitely constrained functional programs with graph-based finite programs, then sparsifying the graph while preserving convergence properties.
- Graph Stein Discrepancies: The computable Stein discrepancy is formulated as an optimization program over functions g ∈G.Its objective is linear in g and depends only on function and gradient values at the discrete sample points.
- Graph Stein Discrepancies: The complete-graph Stein discrepancy is equivalent to the classical discrepancy up to a dimension- and norm-dependent constant κd.Specifically, S(Q, TP, G∥·∥) ≤ S(Q, TP, G∥·∥,Q,G1) ≤ κd S(Q, TP, G∥·∥).
- Geometric Spanners: Because the complete graph imposes O(n^2) constraints, sparse geometric spanners provide an O(n)-constraint alternative with comparable discrepancy values.For a t-spanner, S(Q, TP, G∥·∥,Q,G1) ≤ S(Q, TP, G∥·∥,Q,Gt) ≤ 2t^2 S(Q, TP, G∥·∥,Q,G1).
- Geometric Spanners: A 2-spanner with O(κdn) edges can be computed in O(κdn log(n)) expected time, motivating its adoption as the standard quality measure.The constant κd depends only on dimension d and the selected norm.
- Implementation: The recommended ℓ1 norm decomposes the multivariate optimization into d independent finite-dimensional linear programs that can be solved in parallel.For coordinate-boundary domains, additional compatibility constraints enforce smooth boundary conditions while retaining equivalence to the classical discrepancy.
- Implementation: Algorithm 1 computes the multivariate measure using a sparse 2-spanner, parallel coordinate linear programs, and boundary constraints, while univariate cases use sorting instead.In one dimension, the complete-graph discrepancy can be computed by enforcing constraints only between consecutive sorted sample and boundary points.
5 Experiments
The experiments evaluate Stein discrepancy on exact, biased, and deterministic samples, showing its use for discrepancy comparison, hyperparameter selection, bias-variance assessment, and convergence rates.
- Comparing Discrepancies: For a Gaussian target, i.i.d. Gaussian samples have complete graph Stein discrepancy decay at n^-0.52, while scaled Student’s t samples remain bounded away from zero.The Student’s t distribution matches the Gaussian variance but has 10 degrees of freedom.
- Comparing Discrepancies: The classical Stein discrepancy can be computed in one dimension as a convex quadratically constrained quadratic program with O(n) variables and O(n) constraints.
- Selecting Sampler Hyperparameters: ESS selects a larger SGLD step size than Stein discrepancy, with ESS maximized at ϵ = 5 × 10^-2 and Stein discrepancy minimized at ϵ = 5 × 10^-3.The experiment uses 50 independent sequences of length 1000 and selects the step size by median quality.
- Quantifying a Bias-Variance Trade-off: Approximate RWMH has higher Stein quality under smaller computational budgets but is eventually overtaken by the asymptotically exact sequence.The comparison uses Bayesian logistic regression and 10^5 likelihood evaluations.
- Quantifying a Bias-Variance Trade-off: Additional normalized probability, mean, and second-moment error measures agree with the Stein discrepancy quantification in the approximate-sampling comparison.
- Assessing Convergence Rates: For uniform samples, estimated Stein discrepancy rates are n^-0.49 for i.i.d. sequences, n^-1 for Sobol sequences, and n^-0.96 for kernel herding sequences.The i.i.d. and Sobol rates accord with expected O(1/√n) and O(1/n) bounds, while the herding rate exceeds its best known bound.
6 Discussion of Related Work
The discussion situates the proposed Stein measure among diagnostics for biased and deterministic samples and contrasts its broad test-function class with finite-functional alternatives.
- Related diagnostics: The proposed quality measure compares biased, exact, and deterministic sample sequences by exploiting an infinite class of known target functionals.
- Related diagnostics: Finite-functional diagnostics can lose discriminating power; for a N(0, 1) target, the score statistic cannot distinguish samples with equal first and second moments.
- Deterministic sequences: Figure 5 compares complete graph Stein discrepancy convergence for samples targeting P = Unif(0, 1).
A Proof of Proposition 1
The proof establishes Stein-based bounds through smooth test-function distances, Stein factors, and Wasserstein convergence results under strongly log-concave targets.
- Function distance: The smooth function distance is defined using classes of real-valued functions with continuous derivatives.
- Norms: The general norm framework includes explicitly defined operator norms for vectors, matrices, and tensors.
- Stein factors: For strongly log-concave densities, explicit positive Stein factors support bounds relating the smooth function distance to the Stein discrepancy.
- Stein equation: The Langevin diffusion construction supplies a function solving the Stein equation for sufficiently smooth test functions with bounded derivatives.
- Wasserstein convergence: The proof combines the Stein bound with a smooth-Wasserstein inequality to conclude Wasserstein convergence when the relevant Stein discrepancy converges to zero.
C Proof of Proposition 3: Stein Discrepancy Upper Bound
The proof derives Stein discrepancy upper bounds by comparing expectations under sample and target distributions and applying norm inequalities uniformly over admissible Stein functions.
- Expectation comparison: For any admissible Stein function, the target expectation of its Stein operator is zero, enabling comparison between sample and target expectations.
- Expectation comparison: The expectation difference is decomposed into score-function and gradient terms involving differences between sample and target variables.
- Norm bounds: The second inequality follows from matrix norms, dual norms, Fenchel-Young, and Cauchy-Schwarz inequalities.
- Conclusion: Uniform validity over the admissible function class completes the proof.
D Proof of Proposition 4: Equivalence of Non-uniform Stein Discrepancies
The proof establishes equivalence between Stein discrepancies by exploiting objective linearity, function-class inclusions, and extensions that preserve sample-point values and gradients. A t-spanner argument yields a quantitative comparison between function classes.
- Scaling the test-function class by any positive constant does not change the Stein discrepancy.The objective is linear in g, so scaling the class preserves the normalized discrepancy.
- Function-class inclusion gives the first inequality relating the constrained and broader Stein discrepancies.The proof starts from G∥·∥ ⊆ G∥·∥,Q,G1.
- Whitney-Glaeser extension preserves function values and gradients on the sample support while introducing only the dimension-dependent factor κd.The extension theorem supplies a function in κdG∥·∥ with matching values and gradients at every sample point.
- Because the Stein objective depends only on sample-point values and gradients, the extension yields S(Q, TP, G∥·∥,Q,G1) ≤ κd S(Q, TP, G∥·∥).The preserved sample-point information makes the objective value unchanged before applying the scaling relation.
- The t-spanner property connects arbitrary support points through edges whose lengths control accumulated function and gradient variation.The proof applies the triangle inequality and tensor-norm definition along the spanner path.
- The spanner argument gives S(Q, TP, G∥·∥,Q,Gt) ≤ 2t^2 S(Q, TP, G∥·∥,Q,G1).Thus the discrepancy over the t-controlled class is bounded by a 2t^2 factor times the unit-scale discrepancy.
G Finite-dimensional Classical Stein Program
The finite-dimensional classical Stein program replaces optimization over functions with optimization over their values and derivatives at sorted sample and boundary points. The resulting formulation is a convex quadratically constrained quadratic program with linear objective.
- Theorem 9 formulates the non-uniform classical Stein discrepancy on a sorted set containing sample and finite boundary points.The domain is X = (α, β), with −∞ ≤ α < β ≤ ∞ and sorted values x(1) < ··· < x(n′).
- The program optimizes a Stein objective involving log p(x(i)), g(x(i)), q(x(i)), and g′(x(i)).The objective is given in equation (11a).
- Adjacent-point constraints bound derivatives by c2 and function increments by c2 times the corresponding point spacing.These restrictions appear in equation (11b) for every consecutive sorted pair.
- The notation includes positive-part and boundary-related quantities defined using c3.Equation notation specifies (r)+ ≜ max(r, 0) and defines Lb and Lu through c3.
- The optimization is finite-dimensional because vectors of function values and derivatives at sample or boundary points suffice.Introducing slack variables yields a convex quadratically constrained quadratic program with O(n) constraints, O(n) variables, and a linear objective.
- Extensions preserve the Stein objective because it depends on g and g′ only through their values at sample points.This observation underpins the equivalence between the finite program and the function-class formulation.
G.1 Feasibility of Gc1:3
The feasibility proof shows that constraints on sampled values and derivatives can be extended to functions that are c1-bounded and have c3-Lipschitz, c2-bounded derivatives. It verifies the required bounds using integral inequalities.
- A c2-bounded, c3-Lipschitz derivative must satisfy the program’s sampled derivative constraints.The proof considers such extensions and checks that equation (11b) follows.
- The lower and upper derivative envelopes B and U bound every feasible derivative throughout each interval.Violating either envelope would contradict the c3-Lipschitz property relative to a sample point.
- Integrating the derivative envelopes produces the lower and upper function-increment constraints in equations (11c) and (11d).The proof identifies the resulting integral bounds with the program’s constraints.
- Boundary points satisfy the endpoint condition because the function is zero on the boundary.For interior points, the proof assumes a nonnegative derivative without loss of generality and integrates around the point.
- Integrating the Lipschitz derivative lower bound yields the quadratic constraint linking g(x(i)) and g′(x(i)) to c1.The argument obtains 1/(2c3) g′(x(i))^2 + g(x(i)) ≤ c1, with an analogous bound on the other side.
G.2 Extending Feasible Solutions
The extension construction works interval by interval by interpolating between derivative envelopes that match endpoint derivatives. Convex combinations preserve derivative regularity, while case-specific sign analyses ensure the extended function remains c1-bounded, including unbounded domain tails.
- G.2 Extending Feasible Solutions: Every feasible program solution is extended by constructing lower and upper derivative functions independently on each adjacent interval.The construction requires c2-bounded, c3-Lipschitz functions matching g′ at both interval endpoints.
- G.2 Extending Feasible Solutions: The extension derivative is a convex combination of the interval-wise bounds, with a coefficient chosen to match the required function increment.The construction defines the extension from a pair (mi, Mi) and a ζi ∈ [0, 1].
- G.2 Extending Feasible Solutions: Convexity preserves c2-boundedness and c3-Lipschitzness, so only function boundedness at endpoints and critical points requires verification.The program’s constraint (11e) bounds endpoints, reducing the remaining check to points where the extension derivative vanishes.
- G.2 Extending Feasible Solutions: The envelope functions B and U match endpoint derivatives and bound the derivative throughout each interval, reducing the construction to three sign cases.They serve as the building blocks for selecting mi and Mi.
- G.2 Extending Feasible Solutions: When B and U retain one sign, choosing mi = B and Mi = U makes the extension monotonic and therefore c1-bounded.Monotonicity ensures boundedness for any convex-combination coefficient ζi.
- G.2 Extending Feasible Solutions: When envelopes change signs, roots partition the interval and case-specific choices of mi and Mi control critical-point values within c1.The construction handles one-sign changes using φ and both-sign changes using ψ, with root-based bounds.
- G.2 Extending Feasible Solutions: The two-sign-change construction selects between B, W, and U according to the increment, preserving boundedness or well-definedness at the relevant root.For increments at most ψ, the construction uses B and W; otherwise it uses W and U.
- G.2 Extending Feasible Solutions: The same construction extends the function beyond finite sample extremes when α or β is infinite, while retaining c2-bounded, c3-Lipschitz derivatives and |g| ≤ c1.The proof explicitly treats the left tail and states that the right tail is analogous.
H Equivalence of Constrained Classical and Spanner Stein Discrepancies
For rectangular supports and a t-spanner graph, the graph Stein discrepancy is strongly equivalent to the classical Stein discrepancy, with a dimension-dependent distortion bound.
- The equivalence applies when X is a rectangular support and G_t is a t-spanner of supp(Q).
- A t-spanner graph yields a graph Stein discrepancy bounded below by the classical discrepancy.
- The graph Stein discrepancy is at most t^2κ_d times the classical Stein discrepancy.Here, κ_d depends only on dimension d and is independent of Q, P, G_t, and t.
Proof
The proof establishes the two discrepancy inequalities by constructing compatible boundary extensions and applying Lipschitz bounds, geometric inequalities, and the Whitney-Glaeser extension theorem.
- The first inequality follows from containing the classical Stein set within the constrained graph Stein set.
- For the reverse direction, each constrained test function is extended to a classical Stein function while preserving its values and gradients on supp(Q).The construction enforces zero boundary values and zero off-coordinate derivatives on the coordinate boundary sets.
- The Whitney-Glaeser extension theorem produces a classical Stein function with dimension-dependent factor t^2κ_d and matching Stein discrepancy objective value.
- The extension defines boundary derivatives through a minimum involving the Lipschitz penalty ζ∥z−b∥_1.The resulting derivative remains ζ-Lipschitz on the support and boundary sets.
- Triangle, Hölder, boundary-compatibility, and Lipschitz arguments establish the required regularity bounds before extension.