You are here

MIA Talks

Primer: Submodular maximization and machine learning

September 26, 2018
Depts. of Computer Science and Government, Harvard University

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.