Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing

DOI10.1214/105051606000000772MaRDI QIDQ2467120zbMATH OpenOpenAlexFDO

Authors Yongtao Guan, Stephen M. Krone

Publication date 18 January 2008

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703021

zbMATH Keywords

Cheeger's inequalityconvergencedistributiongeometric ergodicityisoperimetric inequalityMarkov chain Monte Carlo (MCMC) methodsMetropolis-coupled MCMCMetropolis-Hastings chainssmall worldspectral gapstate decomposition

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Probability distributions: general theory (60E05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: We compare convergence rates of Metropolis--Hastings chains to multi-modal target distributions when the proposal distributions can be of ``local and ``small world type. In particular, we show that by adding occasional long-range jumps to a given local proposal distribution, one can turn a chain that is ``slowly mixing (in the complexity of the problem) into a chain that is ``rapidly mixing. To do this, we obtain spectral gap estimates via a new state decomposition theorem and apply an isoperimetric inequality for log-concave probability measures. We discuss potential applicability of our result to Metropolis-coupled Markov chain Monte Carlo schemes.

Review text

A main problem in the Markov chain Monte Carlo (MCMC) methods is to find sampling schemes whose mixing times do not grow too rapidly as the size or complexity of the space is increased. In the present paper the convergence rates of Metropolis-Hastings (MH) chains to multi-modal target distributions, when the proposal distributions are of ``local chain and ``small worlds chains types are compared. The considered state space \(\Omega\) is equipped with two measures: a reference measure taken to be the Lebesgue measure \(\mu\) and a Borel probability measure \(\pi\) which serves as the target distribution. In section 1 the concepts and details of the MH algorithm, geometric ergodicity and the spectral gap which provides a measure of the speed of convergence of a Markov chain to be its stationary measure are described. \textit{J. Cheeger}'s [Probl. Analysis, Sympos. in Honor of Salomon Bochner, Princeton Univ. 1969, 195--199 (1970; Zbl 0212.44903)] inequality is reminded. The notions of log-concave, \(\alpha-\)smooth log-concave functions are given. The notions of slowly mixing and rapidly mixing in the complexity of \(\pi,\) which are given in the terms of the spectral gap, are introduced. Theorem 3.1 gives sufficient conditions that the local MH chain is slowly mixing and the small-world chain is rapidly mixing in the complexity of the multi-modal probability measure \(\pi.\) In section 2 a new version of the state decomposition theorem of \textit{N. Madras} and \textit{D. Randall} [Ann. Appl. Probab. 12, No.~2, 581--606 (2002; Zbl 1017.60080)] is proposed. Theorem 2.2 gives that the spectral gap for the whole MH chain is bounded below by taking into account the mixing speed within each mode and the mixing speed between different modes. In section 3 a lower bound on the conductance for each log-concave piece of the distribution is delivered. Theorem 3.2 is the log-concave version of the isoperimetric inequality of \textit{R. Kannan, L. Lovász} and \textit{M. Simonovits} [Discrete Comput. Geom. 13, No.~3--4, 541--559 (1995; Zbl 0824.52012)]. Theorem 3.4 states a lower bound of the conductance of the MH chain with given transition kernel induced by the uniform \(\delta\)-ball proposal. In section 4 the proof of the main result is exposed. In section 5 possible applications of the obtained results to convergence rates in Metropolis-coupled MCMC are discussed.

Recommendations

• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Fast mixing of Metropolis-Hastings with unimodal targets
• Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces
• Spectral gaps of random walk Metropolis chains
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions

Cites work

• Annealing Markov Chain Monte Carlo with Applications to Ancestral Inference
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Collective dynamics of `small-world' networks
• Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces
• Convex measures on locally convex spaces
• Exclusion and Inclusion Intervals for the Real Eigenvalues of Positive Matrices
• Geometric L² and ^{L1 convergence are equivalent for reversible Markov chains}
• Geometric ergodicity and hybrid Markov chains
• scientific article; zbMATH DE number 3387680 (Why is no real title available?)
• scientific article; zbMATH DE number 3417266 (Why is no real title available?)
• Isoperimetric and analytic inequalities for log-concave probability measures
• Isoperimetric problems for convex bodies and a localization lemma
• Markov chain decomposition for convergence rate analysis
• Monte Carlo sampling methods using Markov chains and their applications
• Optimization by simulated annealing
• Random walks in a convex body and an improved volume algorithm
• The Henselian closures of a PpC field
• Torpid mixing of simulated tempering on the Potts model

Cited in

(14)

• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Sufficient conditions for torpid mixing of parallel and simulated tempering
• Bayesian variable selection regression for genome-wide association studies and other large-scale problems
• Transdimensional transformation based Markov chain Monte Carlo
• Markov chain Monte Carlo based on deterministic transformations
• Fast model-fitting of Bayesian variable selection regression using the iterative complex factorization algorithm
• Fast mixing of Metropolis-Hastings with unimodal targets
• The use of a single pseudo-sample in approximate Bayesian computation
• Simple conditions for metastability of continuous Markov chains
• On‐line partitioning of the sample space in the regional adaptive algorithm
• Dimension-free relaxation times of informed MCMC samplers on discrete spaces
• Geometric Ergodicity of Trans-Dimensional Markov Chain Monte Carlo Algorithms
• Queues with service resetting
• Explicit error bounds for lazy reversible Markov chain Monte Carlo

This page was built for publication: Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467120)