Measuring Sample Quality with Diffusions

Standard Markov chain Monte Carlo diagnostics, like effective sample size, are ineffective for biased sampling procedures that sacrifice asymptotic correctness for computational speed. Recent work addresses this issue for a class of strongly log-concave target distributions by constructing a computable discrepancy measure based on Stein's method that provably determines convergence to the target. We generalize this approach to cover any target with a fast-coupling Ito diffusion by bounding the derivatives of Stein equation solutions in terms of Markov process coupling times. As example applications, we develop computable and convergence-determining diffusion Stein discrepancies for log-concave, heavy-tailed, and multimodal targets and use these quality measures to select the hyperparameters of biased samplers, compare random and deterministic quadrature rules, and quantify bias-variance tradeoffs in approximate Markov chain Monte Carlo. Our explicit multivariate Stein factor bounds may be of independent interest.

• Publication year

  2016

• Venue

  The Annals of Applied Probability

• Publication date

  2016-11-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/19-aap1467arXiv 1611.06972
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Foundations of Modern Probability

  2021cited by this paper
• Robust Statistics

  2018cited by this paper
• Measuring Sample Quality with Kernels

  2017cited by this paper
• A Kernelized Stein Discrepancy for Goodness-of-fit Tests

  2016cited by this paper
• Exploration of the (Non-)Asymptotic Bias and Variance of Stochastic Gradient Langevin Dynamics

  2016cited by this paper
• Dirichlet approximation of equilibrium distributions in Cannings models with mutation

  2016cited by this paper
• Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm

  2016cited by this paper
• Stochastic Differential Equations And Applications

  2016cited by this paper
• Exponential Contraction in Wasserstein Distances for Diffusion Semigroups with Negative Curvature

  2016cited by this paper
• A Kernel Test of Goodness of Fit

  2016cited by this paper
• Operator Variational Inference

  2016cited by this paper
• Black-box Importance Sampling

  2016cited by this paper
• Quantifying the accuracy of approximate diffusions and Markov chains

  2016cited by this paper
• Measuring Sample Quality with Stein's Method

  2015cited by this paper
• Variance Reduction Using Nonreversible Langevin Samplers

  2015cited by this paper
• Control Functionals for Quasi-Monte Carlo Integration

  2015cited by this paper
• Multivariate Stein Factors for a Class of Strongly Log-concave Distributions

  2015cited by this paper
• Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering

  2015cited by this paper
• A Complete Recipe for Stochastic Gradient MCMC

  2015cited by this paper
• Irreversible Langevin samplers and variance reduction: a large deviations approach

  2014cited by this paper
• Stein's method for comparison of univariate distributions

  2014cited by this paper
• Control functionals for Monte Carlo integration

  2014cited by this paper
• Consistency and Fluctuations For Stochastic Gradient Langevin Dynamics

  2014cited by this paper
• A Framework for Computing the Greedy Spanner

  2014influential reference
• Rates of Convergence in Normal Approximation Under Moment Conditions Via New Bounds on Solutions of the Stein Equation

  2013influential reference
• Reflection couplings and contraction rates for diffusions

  2013influential reference
• Computing in Operations Research Using Julia

  2013influential reference
• Stochastic Gradient Riemannian Langevin Dynamics on the Probability Simplex

  2013influential reference
• Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget

  2013influential reference
• Semi Log-Concave Markov Diffusions

  2013cited by this paper
• On the Equivalence between Herding and Conditional Gradient Algorithms

  2012cited by this paper
• Markov Processes: Volume 1

  2012influential reference
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring

  2012cited by this paper
• Bayesian Learning via Stochastic Gradient Langevin Dynamics

  2011cited by this paper
• Handbook of Markov Chain Monte Carlo

  2011influential reference
• Multivariate linear regression with non-normal errors: a solution based on mixture models

  2011cited by this paper
• Riemann manifold Langevin and Hamiltonian Monte Carlo methods

  2011cited by this paper
• Spectral gaps for a Metropolis–Hastings algorithm in infinite dimensions

  2011cited by this paper
• Super-Samples from Kernel Herding

  2010cited by this paper
• A Semigroup Point Of View On Splitting Schemes For Stochastic (Partial) Differential Equations

  2010cited by this paper
• Free Energy Computations: A Mathematical Perspective

  2010cited by this paper
• Kolmogorov Operators in Spaces of Continuous Functions and Equations for Measures

  2009cited by this paper
• Stein's Method of Exchangeable Pairs with Application to the Curie-Weiss Model

  2009cited by this paper
• Convergence of Numerical Time-Averaging and Stationary Measures via Poisson Equations

  2009cited by this paper
• CURVATURE, CONCENTRATION AND ERROR ESTIMATES FOR MARKOV CHAIN MONTE CARLO

  2009cited by this paper
• On Stein's method for multivariate normal approximation

  2009influential reference
• Multivariate normal approximation using Stein's method and Malliavin calculus

  2008influential reference
• Periodic Homogenization Problems in Incompressible Fluid Equations

  2007cited by this paper
• Multivariate normal approximation with Stein’s method of exchangeable pairs under a general linearity condition

  2007influential reference
• MULTIVARIATE NORMAL APPROXIMATION USING EXCHANGEABLE PAIRS

  2007influential reference
• Stochastic Processes and Applications

  2007cited by this paper
• Small Manhattan Networks and Algorithmic Applications for the Earth Mover ’ s Distance

  2007cited by this paper
• An Introduction to Interpolation Theory

  2007cited by this paper
• Multilevel (Hierarchical) Modeling: What It Can and Cannot Do

  2006cited by this paper
• The Whitney extension problem and Lipschitz selections of set-valued mappings in jet-spaces

  2006cited by this paper
• Output Assessment for Monte Carlo Simulations via the Score Statistic

  2006cited by this paper
• A Kernel Method for the Two-Sample-Problem

  2006cited by this paper
• Kolmogorov equations in infinite dimensions: Well-posedness and regularity of solutions, with applications to stochastic generalized Burgers equations

  2005cited by this paper
• Use of exchangeable pairs in the analysis of simulations

  2004cited by this paper
• Conditional Path Sampling of SDEs and the Langevin MCMC Method

  2004cited by this paper
• Fast construction of nets in low dimensional metrics, and their applications

  2004cited by this paper
• Normal Approximation by Stein ’ s Method

  2003cited by this paper
• Langevin Diffusions and Metropolis-Hastings Algorithms

  2002cited by this paper
• Multiple View Geometry in Computer Vision

  2001cited by this paper
• Second Order Pde's in Finite and Infinite Dimension: A Probabilistic Approach

  2001cited by this paper
• Infinite-Dimensional Dynamical Systems: An Introduction to Dissipative Parabolic PDEs and the Theory of Global Attractors

  2001cited by this paper
• Functions of Bounded Variation and Free Discontinuity Problems

  2000cited by this paper
• Applications of Malliavin calculus to Monte Carlo methods in finance

  1999cited by this paper
• One-parameter semigroups for linear evolution equations

  1999cited by this paper
• Convection ± di usion equation with space ± time ergodic random

  1998cited by this paper
• Convection–diffusion equation with space–time ergodic random flow

  1998cited by this paper
• Integral Probability Metrics and Their Generating Classes of Functions

  1997cited by this paper
• Exponential convergence of Langevin distributions and their discrete approximations

  1996cited by this paper
• Bayesian robust multivariate linear regression with incomplete data

  1996cited by this paper
• Bayesian Data Analysis.

  1996cited by this paper
• Gibbs Sampler Convergence Criteria

  1995influential reference
• Accelerating Gaussian Diffusions

  1993cited by this paper
• Graph Spanners: a Survey

  1992cited by this paper
• Markov Chain Monte Carlo Maximum Likelihood

  1991cited by this paper
• On the Rate of Convergence in the Multivariate CLT

  1991cited by this paper
• Stein's method for diffusion approximations

  1990influential reference
• Stochastic integration and differential equations

  1990cited by this paper
• Graph spanners

  1989cited by this paper
• Stein's method and poisson process convergence

  1988cited by this paper
• The second order Langevin equation and numerical simulations

  1987cited by this paper
• Stochastic differential equations : an introduction with applications

  1987cited by this paper
• There is a planar graph almost as good as the complete graph

  1986cited by this paper
• The Fokker-Planck equation : methods of solution and applications

  1985cited by this paper
• Stochastic Stability of Differential Equations

  1980cited by this paper
• Generalised P-representations in quantum optics

  1980cited by this paper
• Quantum theory of optical bistability. I. Nonlinear polarisability model

  1980cited by this paper
• Time-reversible diffusions

  1978cited by this paper
• Bayesian and Non-Bayesian Analysis of the Regression Model with Multivariate Student- t Error Terms

  1976cited by this paper
• Calculation of the Wasserstein Distance Between Probability Distributions on the Line

  1974cited by this paper
• A bound for the error in the normal approximation to the distribution of a sum of dependent random variables

  1972cited by this paper
• Markov Processes

  1968cited by this paper
• Étude de Quelques Algèbres Tayloriennes

  1958influential reference

• Efficient Learning of Stationary Diffusions with Stein-type Discrepancies

  2026influential citation
• Some notes on quantitative generalized CLTs with self-decomposable limiting laws by spectral methods

  2025cites this paper
• Correcting Mode Proportion Bias in Generalized Bayesian Inference via a Weighted Kernel Stein Discrepancy

  2025cites this paper
• Fast and scalable score-based kernel calibration tests

  2025cites this paper
• Stein's method for marginals on large graphical models

  2024cites this paper
• Statistical Error of Numerical Integrators for Underdamped Langevin Dynamics with Deterministic And Stochastic Gradients

  2024influential citation
• Physics‐reliable frugal local uncertainty analysis for full waveform inversion

  2024cites this paper
• Efficient Sampling on Riemannian Manifolds via Langevin MCMC

  2024cites this paper
• Gradient-free kernel conditional stein discrepancy goodness of fit testing

  2023cites this paper
• A Stein's Method Approach to the Linear Noise Approximation for Stationary Distributions of Chemical Reaction Networks

  2023influential citation
• Fast and Scalable Score-Based Calibration Tests

  2023cites this paper
• A Kernelized Stein Discrepancy for Biological Sequences

  2023influential citation
• Bayesian Numerical Integration with Neural Networks

  2023cites this paper
• Stein Π-Importance Sampling

  2023cites this paper
• Physics reliable frugal uncertainty analysis for full waveform inversion

  2023cites this paper
• Transportation onto log-Lipschitz perturbations

  2023cites this paper
• Using Perturbation to Improve Goodness-of-Fit Tests based on Kernelized Stein Discrepancy

  2023influential citation
• Mean-Square Analysis of Discretized Itô Diffusions for Heavy-tailed Sampling

  2023cites this paper
• HOW GOOD IS YOUR LAPLACE APPROXIMATION OF THE BAYESIAN POSTERIOR? FINITE-SAMPLE COMPUTABLE ERROR BOUNDS FOR A VARIETY OF USEFUL DIVERGENCES BY MIKOŁAJ

  2023cites this paper
• Gradient-Free Kernel Stein Discrepancy

  2022influential citation
• Regularized Stein Variational Gradient Flow

  2022cites this paper
• Controlling Moments with Kernel Stein Discrepancies

  2022influential citation
• Posterior sampling with CNN-based, Plug-and-Play regularization with applications to Post-Stack Seismic Inversion

  2022cites this paper
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents

  2022cites this paper
• Targeted Separation and Convergence with Kernel Discrepancies

  2022influential citation
• Towards Healing the Blindness of Score Matching

  2022cites this paper
• HOW GOOD IS YOUR GAUSSIAN APPROXIMATION OF THE POSTERIOR? FINITE-SAMPLE COMPUTABLE ERROR BOUNDS FOR A VARIETY OF USEFUL DIVERGENCES

  2022cites this paper
• Understanding the Variance Collapse of SVGD in High Dimensions

  2022cites this paper
• Generative Models: An Interdisciplinary Perspective

  2022cites this paper
• Convergence of Position-Dependent MALA with Application to Conditional Simulation in GLMMs

  2021cites this paper
• Geometry-informed irreversible perturbations for accelerated convergence of Langevin dynamics

  2021cites this paper
• Sampling with Mirrored Stein Operators

  2021cites this paper
• Interpreting diffusion score matching using normalizing flow

  2021cites this paper
• Stein’s Method Meets Statistics: A Review of Some Recent Developments

  2021influential citation
• A Unifying and Canonical Description of Measure-Preserving Diffusions

  2021cites this paper
• Robust generalised Bayesian inference for intractable likelihoods

  2021influential citation
• Post-Processing of MCMC

  2021cites this paper
• Stein’s density method for multivariate continuous distributions

  2021cites this paper
• The Prelimit Generator Comparison Approach of Stein’s Method

  2021cites this paper
• Stein’s Method Meets Computational Statistics: A Review of Some Recent Developments

  2021influential citation
• De-randomizing MCMC dynamics with the generalized Stein operator

  2021influential citation
• Standardisation-function Kernel Stein Discrepancy: A Unifying View on Kernel Stein Discrepancy Tests for Goodness-of-fit

  2021influential citation
• Bounding Wasserstein Distance with Couplings

  2021influential citation
• De-randomizing MCMC dynamics with the diffusion Stein operator

  2021cites this paper
• Bayesian seismic inversion: a fast sampling Langevin dynamics Markov chain Monte Carlo method

  2021cites this paper
• On Reference Solutions to Non-Gaussian SLAM Factor Graphs

  2021cites this paper
• Vector-Valued Control Variates

  2021cites this paper
• Coupling‐based convergence assessment of some Gibbs samplers for high‐dimensional Bayesian regression with shrinkage priors

  2020cites this paper
• A Wasserstein Minimum Velocity Approach to Learning Unnormalized Models

  2020cites this paper
• The reproducing Stein kernel approach for post-hoc corrected sampling

  2020influential citation
• Steady-state diffusion approximations of Markov chains: error analysis via the discrete Poisson equation

  2020influential citation
• Wasserstein Rate Driven CLTs for Markov Chains with Weighted Lipschitz, Sobolev, and Stein Test Functions

  2020cites this paper
• Scalable Approximate Inference and Some Applications

  2020cites this paper
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness

  2020cites this paper
• A survey of Monte Carlo methods for parameter estimation

  2020cites this paper
• Scalable Control Variates for Monte Carlo Methods via Stochastic Optimization

  2020cites this paper
• Stochastic Stein Discrepancies

  2020cites this paper
• Convergence Analysis of Langevin Monte Carlo in Chi-Square Divergence

  2020cites this paper
• Convergence Rates for Langevin Monte Carlo in the Nonconvex Setting

  2020cites this paper
• Blindness of score-based methods to isolated components and mixing proportions

  2020influential citation
• Optimal Quantisation of Probability Measures Using Maximum Mean Discrepancy

  2020cites this paper
• Bayesian seismic inversion: Measuring Langevin MCMC sample quality with kernels

  2020cites this paper
• Stability estimates for invariant measures of diffusion processes, with applications to stability of moment measures and Stein kernels

  2020cites this paper
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method

  2020cites this paper
• The Interplay between Sampling and Optimization

  2020cites this paper
• Validated Variational Inference via Practical Posterior Error Bounds

  2019cites this paper
• Stein’s method for the Poisson–Dirichlet distribution and the Ewens sampling formula, with applications to Wright–Fisher models

  2019cites this paper
• Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT

  2019cites this paper
• Practical Posterior Error Bounds from Variational Objectives

  2019cites this paper
• Understanding MCMC Dynamics as Flows on the Wasserstein Space

  2019cites this paper
• Autour de l'algorithme du Langevin : extensions et applications

  2019cites this paper
• Improved bounds for discretization of Langevin diffusions: Near-optimal rates without convexity

  2019cites this paper
• On Stein’s method for multivariate self-decomposable laws

  2019cites this paper
• Stochastic Gradient Markov Chain Monte Carlo

  2019cites this paper
• Quantitative W1 Convergence of Langevin-Like Stochastic Processes with Non-Convex Potential State-Dependent Noise

  2019cites this paper
• PR ] 1 3 N ov 2 01 9 Stein operators , kernels and discrepancies for multivariate continuous distributions

  2019cites this paper
• A Kernel Stein Test for Comparing Latent Variable Models

  2019cites this paper
• Minimum Stein Discrepancy Estimators

  2019cites this paper
• First-order covariance inequalities via Stein’s method

  2019cites this paper
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond

  2019cites this paper
• Stein’s method and the distribution of the product of zero mean correlated normal random variables

  2019cites this paper
• Estimating Convergence of Markov chains with L-Lag Couplings

  2019cites this paper
• L G ] 8 M ay 2 01 9 Adaptive MCMC via Combining Local Samplers

  2019influential citation
• Stein Point Markov Chain Monte Carlo

  2019cites this paper
• Official Journal of the Bernoulli Society for Mathematical Statistics and Probability

  2019cites this paper
• Towards Characterizing the High-dimensional Bias of Kernel-based Particle Inference Algorithms

  2019cites this paper
• Stochastic Gradient and Langevin Processes

  2019cites this paper
• Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting

  2018cites this paper
• Stein Points

  2018cites this paper
• Multivariate approximations in Wasserstein distance by Stein’s method and Bismut’s formula

  2018cites this paper
• Stein-type covariance identities: Klaassen, Papathanasiou and Olkin-Shepp type bounds for arbitrary target distributions

  2018cites this paper
• On Stein’s method for multivariate self-decomposable laws with finite first moment

  2018cites this paper
• Nonasymptotic bounds for sampling algorithms without log-concavity

  2018cites this paper
• Sobolev Descent

  2018cites this paper
• Scaling Bayesian inference: theoretical foundations and practical methods

  2018influential citation
• Multivariate approximations in Wasserstein distance by Stein’s method and Bismut’s formula

  2018cites this paper
• Stein operators, kernels and discrepancies for multivariate continuous distributions

  2018cites this paper
• A Riemannian-Stein Kernel method

  2018cites this paper
• Global Non-convex Optimization with Discretized Diffusions

  2018influential citation
• Practical bounds on the error of Bayesian posterior approximations: A nonasymptotic approach

  2018cites this paper