Annealing and Tempering for Sampling and Counting

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/16323

Title: Annealing and Tempering for Sampling and Counting
Author: Bhatnagar, Nayantara
Abstract: The Markov Chain Monte Carlo (MCMC) method has been widely used in practice since the 1950's in areas such as biology, statistics, and physics. However, it is only in the last few decades that powerful techniques for obtaining rigorous performance guarantees with respect to the running time have been developed. Today, with only a few notable exceptions, most known algorithms for approximately uniform sampling and approximate counting rely on the MCMC method. This thesis focuses on algorithms that use MCMC combined with an algorithm from optimization called simulated annealing, for sampling and counting problems. Annealing is a heuristic for finding the global optimum of a function over a large search space. It has recently emerged as a powerful technique used in conjunction with the MCMC method for sampling problems, for example in the estimation of the permanent and in algorithms for computing the volume of a convex body. We examine other applications of annealing to sampling problems as well as scenarios when it fails to converge in polynomial time. We consider the problem of randomly generating 0-1 contingency tables. This is a well-studied problem in statistics, as well as the theory of random graphs, since it is also equivalent to generating a random bipartite graph with a prescribed degree sequence. Previously, the only algorithm known for all degree sequences was by reduction to approximating the permanent of a 0-1 matrix. We give a direct and more efficient combinatorial algorithm which relies on simulated annealing. Simulated tempering is a variant of annealing used for sampling in which a temperature parameter is randomly raised or lowered during the simulation. The idea is that by extending the state space of the Markov chain to a polynomial number of progressively smoother distributions, parameterized by temperature, the chain could cross bottlenecks in the original space which cause slow mixing. We show that simulated tempering mixes torpidly for the 3-state ferromagnetic Potts model on the complete graph. Moreover, we disprove the conventional belief that tempering can slow fixed temperature algorithms by at most a polynomial in the number of temperatures and show that it can converge at a rate that is slower by at least an exponential factor.
Type: Dissertation
URI: http://hdl.handle.net/1853/16323
Date: 2007-07-09
Publisher: Georgia Institute of Technology
Subject: Annealing
Markov Chain Monte Carlo
Markov chains
Discrete probability
Algorithms
Theoretical computer science
Simulated tempering
Department: Algorithms, Combinatorics, and Optimization
Computing
Advisor: Committee Chair: Dr. Dana Randall; Committee Chair: Dr. Eric Vigoda; Committee Member: Dr. Prasad Tetali; Committee Member: Dr. Robin Thomas; Committee Member: Dr. Santosh Vempala
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
bhatnagar_nayantara_200708_phd.pdf 693.9Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record