Principal Investigator Stefanie Jegelka
Submodular set functions are characterized by an intuitive diminishing marginal costs property. They have long been important in combinatorics and many other areas, and it turns out that they can help model interesting complex interactions in machine learning problems too. Luckily, their structure admits efficient (approximate) optimization algorithms in many settings. Unfortunately, however, not all set functions are submodular, and I am collecting a growing list of functions that may appear submodular at first look but are actually not.
Professor Jegelka is interested in how we can efficiently use submodularity in machine learning, and what new interesting (combinatorial) models are possible. The first projects below address the efficient minimization of submodular functions, and the others the effect and complexity of having submodular functions on graph edges.