Approximating Partition Functions in Constant Time

Understand

We study approximations of the partition function of dense graphical models.

• Partition functions of graphical models play a fundamental role is statistical physics, in statistics and in machine learning.
• Two of the main methods for approximating the partition function are Markov Chain Monte Carlo and Variational Methods.
• An impressive body of work in mathematics, physics and theoretical computer science provides conditions under which Markov Chain Monte Carlo methods converge in polynomial time.