Ó³»­´«Ã½

Submodular functions are ubiquitous in machine learning, with applications ranging from item recommendation systems to feature selection, clustering, network analysis, document summarization, and Bayesian optimization. These functions capture a key property that is common to many problems: we experience diminishing returns as we select additional items (or features, clusters, nodes, keyphrases, etc.). In this talk, we will survey submodular functions in a variety of salient applications and show why maximizing such functions is challenging. We will then describe simple approximation algorithms with provably optimal guarantees and glimpse into cutting edge research.