Title: Calculating Partition Functions Using Convex Programming: Provable Bounds for Variational Methods
Speaker: Andrej Risteski, Princeton University
Date: Wednesday, October 19, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
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.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/