Adaptive simulated annealing: A near-optimal connection between sampling and counting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adaptive simulated annealing: A near-optimal connection between sampling and counting

Full text

Pdf (288 KB)

Source

Journal of the ACM (JACM) archive
Volume 56 , Issue 3 (May 2009) table of contents

Article No. 18

Year of Publication: 2009

ISSN:0004-5411

Authors

Daniel Štefankovič	University of Rochester, Rochester, NY
Santosh Vempala	Georgia Institute of Technology, Atlanta, GA
Eric Vigoda	Georgia Institute of Technology, Atlanta, GA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 202, Citation Count: 1

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1516512.1516520 What is a DOI?

ABSTRACT

We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function Z of a discrete system, such as the Ising model, matchings or colorings of a graph. The typical approach to estimating the partition function Z(β^*) at some desired inverse temperature β^* is to define a sequence, which we call a cooling schedule, β₀ = 0 < β₁ < … < β _ℓ = β^* where Z(0) is trivial to compute and the ratios Z(β_i+1)/Z(β_i) are easy to estimate by sampling from the distribution corresponding to Z(β_i). Previous approaches required a cooling schedule of length O^*(ln A) where A=Z(0), thereby ensuring that each ratio Z(β_i+1)/Z(β_i) is bounded. We present a cooling schedule of length ℓ =O^*(&sqrt; lnA).

For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of colorings or matchings of a graph, our cooling schedule is of length O^*(&sqrt; n), which implies an overall savings of O^*(n) in the running time of the approximate counting algorithm (since roughly ℓ samples are needed to estimate each ratio).

A similar improvement in the length of the cooling schedule was recently obtained by Lovász and Vempala in the context of estimating the volume of convex bodies. While our reduction is inspired by theirs, the discrete analogue of their result turns out to be significantly more difficult. Whereas a fixed schedule suffices in their setting, we prove that in the discrete setting we need an adaptive schedule, that is, the schedule depends on Z. More precisely, we prove any nonadaptive cooling schedule has length at least O^*(ln A), and we present an algorithm to find an adaptive schedule of length O^*(&sqrt; ln A).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Babai, L. 1979. Monte-carlo algorithms in graph isomorphism testing. Tech. Rep. 79-10, Université de Montréal, Montréal, Quebec.
	2	Ivona Bezáková , Daniel Štefankovič , Vijay V. Vazirani , Eric Vigoda, Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems, SIAM Journal on Computing, v.37 n.5, p.1429-1454, January 2008 [doi>10.1137/050644033]
	3	Dyer, M., and Frieze, A. 1991. Computing the volume of convex bodies: a case where randomness provably helps. In Probabilistic combinatorics and its applications. Proceedings of Symposiusm on Applied Mathematics, vol. 44. American Mathematics Society, Providence, RI, 123--169.
	4	Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
	5	Ferrenberg, A. M., and Swendsen, R. H. 1988. New Monte Carlo technique for studying phase transitions. Phys. Rev. Lett. 61, 23 (December), 2635+.
	6	Frieze, A., and Vigoda, E. 2007. A survey on the use of Markov chains to randomly sample colourings. In Combinatorics, complexity, and chance. Oxford Lecture Ser. Math. Appl., vol. 34. Oxford Univ. Press, Oxford, UK, 53--71.
	7	David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
	8	Janson, S., Luczak, T., and Rucinski, A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York.
	9	Mark Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures & Algorithms, v.7 n.2, p.157-165, September 1995 [doi>10.1002/rsa.3240070205]
	10	Jerrum, M. 2003. Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel.
	11	M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
	12	Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
	13	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	14	Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
	15	Laszlo Lovasz , Santosh Vempala, Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.57-68, October 21-24, 2006 [doi>10.1109/FOCS.2006.28]
	16	László Lovász , Santosh Vempala, Simulated annealing in convex bodies and an O^*(n⁴) volume algorithm, Journal of Computer and System Sciences, v.72 n.2, p.392-417, March 2006 [doi>10.1016/j.jcss.2005.08.004]
	17	Martinelli, F. 2004. Relaxation times of Markov chains in statistical mechanics and combinatorial structures. In Probability on Discrete Structures. Encyclopaedia Math. Sci., vol. 110. Springer-Verlag, Berlin, Germany, 175--262.
	18	Martinelli, F., and Olivieri, E. 1994. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys. 161, 3, 447--486.
	19	Salsburg, Z. W., Jacobson, J. D., Fickett, W., and Wood, W. W. 1959. Application of the Monte Carlo method to the lattice-gas model. J. Chem. Phys. 30, 1, 65--72.
	20	Valleau, J. P., and Card, D. N. 1972. Monte Carlo estimation of the free energy by multistage sampling. J. Chem. Phys. 57, 12, 5457--5462.
	21	Vempala, S. 2005. Geometric random walks: A survey. In Combinatorial and computational geometry. Math. Sci. Res. Inst. Publ., vol. 52. Cambridge Univ. Press, Cambridge, MA, 577--616.
	22	Vigoda, E. 2001. A note on the Glauber dynamics for sampling independent sets. Electron. J. Combin. 8, 1, Research Paper 8, 8 pp. (electronic).
	23	Dror Weitz , Alistair Sinclair, Mixing in time and space for discrete spin systems, University of California, Berkeley, 2004
	24	Dror Weitz, Counting independent sets up to the tree threshold, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132538]