### Adaptive simulated annealing: A near-optimal connection between sampling and countingAdaptive simulated annealing: A near-optimal connection between sampling and counting Access Restriction
Subscribed

 Author tefankovi, Daniel ♦ Vempala, Santosh ♦ Vigoda, Eric Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Counting ♦ Markov chain Monte Carlo ♦ Simulated annealing 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 $\textit{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}$ = 0 < $β_{1}$ < … < β $_{ℓ}$ = $β^{*}$ where $\textit{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$ $\textit{A})$ where $\textit{A}=\textit{Z}(0),$ thereby ensuring that each ratio $Z(β_{i+1})/Z(β_{i})$ is bounded. We present a cooling schedule of length ℓ $=O^{*}(&sqrt;$ $ln\textit{A}).$ 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;$ $\textit{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 $\textit{Z}.$ More precisely, we prove any nonadaptive cooling schedule has length at least $O^{*}(ln$ $\textit{A}),$ and we present an algorithm to find an adaptive schedule of length $O^{*}(&sqrt;$ ln $\textit{A}).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 3 Page Count 36 Starting Page 1 Ending Page 36

#### Open content in new tab

Source: ACM Digital Library