 |
Center for Nonlinear Studies |
"The problem of approximating partition functions for graphical models is a very fundamental one: from a practical point of view it is linked intimately to common tasks like calculating marginals in the model and sampling from the model; from a theoretical it is linked to understanding the class #P, which intuitively captures counting problems. We give provable bounds for algorithms that are based on variational methods: a technique which is very popular in practice but rather poorly understood theoretically in comparison to MCMC methods. We make use of recent tools in combinatorial optimization: the Sherali-Adams and Lasserre convex programming hierarchies to get algorithms for "dense" Ising models. These techniques give new, non-trivial approximation guarantees for the partition function beyond the regime of correlation decay. They also generalize some classical results from statistical physics about the Curie-Weiss ferromagnetic Ising model, as well as provide a partition function counterpart of classical results about max-cut on dense graphs. With this, we connect techniques from two apparently disparate research areas -- optimization and counting/partition function approximations. Time permitting, we also will show worst-case guarantees for coarse (multiplicative) approximations to the log-partition functions in the worst-case setting (i.e. for arbitrary Ising models). "
Host: Michael Chertkov