Submodular functions and machine learning

Many problems in machine learning that involve discrete structures or subset selection may be phrased in the language of submodular set functions. The property of submodularity, also referred to as a 'discrete analog of convexity', expresses the notion of diminishing marginal returns, and captures combinatorial versions of rank and dependence. Submodular functions occur in a variety of areas including graph theory, information theory, combinatorial optimization, stochastic processes and game theory. In machine learning, they emerge in different forms as the potential functions of graphical models, as the utility functions in active learning and sensing, in models of diversity, in structured sparse estimation or network inference.
The lectures will give an introduction to the theory of submodular functions, their applications in machine learning and related optimization problems.

Part I of the lectures will introduce the concept of submodularity along with several examples, as well as associated polyhedra and relations to convexity. Part II will address the ideas underlying algorithms for minimizing and maximizing submodular functions. For example, those algorithms exploit ties to both convexity and concavity.