Submodularity, Polyhedral Geometry and Projection Methods

Submodularity is an important concept in combinatorial optimization, graph theory, game theory, and, more recently, machine learning, signal processing and computer vision, where practical algorithms are a major concern. Often, the submodular functions occurring in practice have additional structure that can be exploited for practical optimization algorithms.

In this talk, I will focus on the special case of decomposable submodular minimization. Starting with an introduction to basic concepts, polyhedra and relations to convexity, I will outline how to exploit decomposability to obtain easy-to-use algorithms that can minimize such functions by solving a best approximation problem. Our algorithms solve both the convex relaxation and the original discrete problem. We observe that these algorithms work well in practice, and analyze their convergence properties.

This is joint work with Robert Nishihara, Suvrit Sra, Francis Bach and Michael I. Jordan.