Calendar

Location: CoRE 301

Abstract: The problem of approximating partition functions for graphical models is a very important one: from a practical point of view it is linked intimately to common tasks like calculating marginals 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 Markov Chain Monte Carlo methods.
We make use of recent tools in combinatorial optimization: the Sherali-Adams and Sum of Squares 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 model, as well as provide a partition function counterpart of classical results about max-cut on dense graphs.
With this, we connect tools from two apparently disparate research areas -- optimization and counting/partition function approximations. Our proof techniques are very simple and generic, and likely to be applicable to other settings.