Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Submodularity allows one to efficiently find provably optimal or near-optimal solutions to discrete problems. Submodular minimization has found use, e.g., in graphical model inference and clustering, whereas maximization has been applied, e.g., to variable/feature selection and active learning. Submodularity, however, is still only beginning to show applicability in machine learning and its applications. Moreover, work on submodular optimization in the combinatorics and operations research literature has been primarily unaware of unique problems arising in machine learning. Therefore, existing standard algorithms do not exploit certain structures or variants of the submodular problems arising in machine learning. Studying novel machine learning problems involving submodular objectives can thus lead to advances in the pure combinatorics literature. We propose to pursue activities that bring together research in machine learning and combinatorial optimization to solve problems which neither of the communities can solve alone.
In particular, we propose to use insights from machine learning to enable scaling up typical submodular optimization problem sizes (by focusing on problem instances arising in learning). We also propose to further chart the territory that submodularity plays in machine learning. In this grant, we will introduce new submodular structures specifically related to submodularity. We will introduce submodular learning problems for machine learning. We will introduce new submodular optimization problems with constraints. And lastly, we will apply these submodular instances to real-world applications in computer vision, speech recognition, and natural language processing.
