[Colloquium] Fwd: [Theory] Dec 14 1:30pm Stefankovic: Adaptive annealing

[Margery Ishmael]

Begin forwarded message:

> From: theory at mailman.cs.uchicago.edu
> Date: December 1, 2006 12:15:57 PM CST
> To: theory at cs.uchicago.edu
> Subject: [Theory] Dec 14 1:30pm Stefankovic: Adaptive annealing
> Reply-To: theory at mailman.cs.uchicago.edu
>
>
>
>               UNIVERSITY OF CHICAGO
>           DEPARTMENT OF COMPUTER SCIENCE
>                 THEORY SEMINAR
>
> Date:  Thursday, December 14, 1:30 pm
>
> Location:  Ryerson 251
>
> Speaker: Daniel Stefankovic (University of Rochester)
>
> 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.
>
> --------
>
> Host: Laci Babai   lbabai at cs.uchicago.edu
>
>
> _______________________________________________
> Theory mailing list
> Theory at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/theory
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20061201/b8d987f4/attachment.htm