ACO Home Page   Admission Information Program Description Affiliated Faculty Students Alumni Research Program ACO News ACO Events ACO Internal   Georgia Tech College of Computing School of Ind. Sys. Eng. School of Mathematics School of Electrical Eng.   Help Advanced Search   Contact WEBmaster

Final doctoral examination and defense of dissertation of Nayantara Bhatnagar

Title: Annealing and Tempering for Sampling and Counting

Time:	Friday, June 22, 1:00pm
Location:	Klaus 2108
Advisors:	Drs. Dana Randal and Eric Vigoda
Committee:	Dr. Dana Randall, College of Computing
	Dr. Eric Vigoda, College of Computing
	Dr. Prasad Tetali, School of Mathematics
	Dr. Robin Thomas, School of Mathematics
	Dr. Santosh Vempala, College of Computing
Reader:	Dr. Prasad Tetali, School of Mathematics

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 algorithms for approximate sampling and 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 make progress towards understanding when annealing can be applied 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. An interesting aspect of the annealing algorithm is that the high temperature distribution for the annealing is defined algorithmically.

Simulated tempering is a variant of annealing where the state space of the Markov chain is extended to a polynomial number of progressively smoother distributions, parametrized by temperature. During the simulation, the temperature is allowed to vary randomly. We show that simulated tempering takes exponential time to converge for sampling from configurations of the 3-state ferromagnetic Potts model on the complete graph. Furthermore, the rate of convergence is slower than the algorithm at a fixed temperature by at least an exponential factor, disproving the conventional belief that in the worst case tempering could slow down the fixed temperature algorithm by at most a polynomial factor.

<Plain-Text Page>  (ACO Program Web Pages)

. . . . . . . . . . . . . .

This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: May 20, 2009 Georgia Tech Disclaimer: Notwithstanding any language to the contrary, nothing contained herein constitutes nor is intended to constitute an offer, inducement, promise, or contract of any kind. The data contained herein is for informational purposes only and is not represented to be error free. Any links to non-Georgia Tech information are provided as a courtesy. They are not intended to nor do they constitute an endorsement by the Georgia Institute of Technology of the linked materials.