Monday, November 06, 2006
11:00 AM
CSB 209
Daniel Stefankovic
U. Rochester
Adaptive Annealing: A Near-optimal Connection between Sampling and Counting Partition Functions
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, the permanent, or colorings of a graph. The typical approach to estimating the partition function $Z(\beta^*)$ at some desired (inverse) temperature $\beta^*$ is to define a sequence, which we call a {\em cooling schedule}, $\beta_0=0<\beta_1<\dots<\beta_\ell=\beta^*$ where $Z(0)$ is trivial to compute and the ratios $Z(\beta_{i+1})/Z(\beta_i)$ are easy to estimate by sampling from the distribution corresponding to $Z(\beta_i)$. Previous approaches required a cooling schedule of length $O^*(\ln{A})$ where $A=Z(0)$, thereby ensuring that each ratio $Z(\beta_{i+1})/Z(\beta_i)$ is bounded. We present a cooling schedule of length $O^*(\sqrt{\ln{A}})$. For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of $k$-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 $\ell$ samples are needed to estimate each ratio).

A similar improvement in the length of the cooling schedule was recently obtained by Lov\'asz and Vempala \cite{LV1} for estimating the volume of convex bodies and this was an important ingredient in reducing the complexity from $O^*(n^5)$ to $O^*(n^4)$. 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, i.\,e., the schedule depends on $Z$. More precisely, we prove any non-adaptive 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}})$.

(Joint work with Santosh Vempala and Eric Vigoda.)