Location: Other - CoRE 301
Date & time: Wednesday, 19 October 2016 at 11:00AM - 11:11AM
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.'