Submodularity in Machine Learning and Vision

Numerous problems in machine learning and vision are inherently discrete. More often than not, these lead to challenging optimization problems. While convexity is an important property when solving continuous optimization problems, submodularity, often viewed as a discrete analog of convexity, is key to solving many discrete problems. Its characterizing property, diminishing marginal returns, appears naturally in a multitude of settings. While submodularity has long been recognized in combinatorial optimization and game theory, it has seen a recent surge of interest in theoretical computer science, machine learning and computer vision. This tutorial will introduce the concept of submodularity and its basic properties, and outline recent research directions -- such as new approaches towards large-scale optimization and sequential decision making tasks. We will discuss recent applications to challenging machine learning and vision problems such as high-order graphical model inference, structured sparse modeling, multiple object detection, active sensing etc. The tutorial will not assume any specific prior knowledge on the subject.