Dept Banner
Dept Banner

Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Andrej Risteski, Princeton University

Location:  CoRE 301
Date & time: Wednesday, 19 October 2016 at 11:00AM -

Andrej Risteski, Princeton University

"Calculating partition functions using convex programming: provable bounds for variational methods"
 
Time: 11:00 AM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530