[Colloquium] Talk by Daniel Stefankovic on Thurs. December 14, 2006

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE - TALK REMINDER

Date: Thursday, December 14, 2006
Time: 1:30 p.m.
Place: Ryerson 251

-------------------------------------------

Speaker: DANIEL STEFANKOVIC (University of Rochester)

Url: http://www.cs.rochester.edu/~stefanko/

Title: Adaptive Annealing: A Near-optimal Connection between Sampling
        and Counting Partition Functions

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,
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.

***The talk will be followed by refreshments in Ryerson 255***

--------

Host: Laci Babai   lbabai at cs.uchicago.edu