Most engineering and science problems involve modeling. We need inference calculations to draw predictions from the models or to estimate them from available measurements. In many cases the inference calculations can be done only approximately as in decoding, sensor networks, or in modeling biological systems. At the core, inference tasks tie together three types of problems: counting (partition function), geometry (valid marginals), and uncertainty (entropy). Most approximate inference methods can be viewed as different ways of simplifying this three-way combination. Much of recent effort has been spent on developing and understanding distributed approximation algorithms that reduce to local operations in an effort to solve a global problem. In this talk I will provide an optimization view of approximate inference algorithms, exemplify recent advances, and outline some of the many open problems and connections that are emerging due to modern applications.

Based on joint work with Amir Globerson and David Sontag.