Overview
This page collects some material and references related to submodular optimization,
in particular in machine learning and AI.
Convex optimization has become a main workhorse for many machine
learning algorithms during the past ten years. When minimizing a convex
loss function for, e.g., training a Support Vector Machine, we can rest
assured to efficiently find an optimal solution, even for large
problems. In recent years, another fundamental problem structure, which
has similar beneficial properties, has emerged as very useful in a
variety of machine learning applications:
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.
Similarly to convexity, submodularity allows one to efficiently find provably
(near-)optimal solutions.
- Modern Aspects of Submodularity workshop at GeorgiaTech organized by Shabbir Ahmed, Nina Balcan, Satoru Iwata and Prasad Tetali
- NIPS 2011 Workshop on Discrete Optimization in Machine Learning: Uncertainty, Generalization adn Feedback organized by Andreas Krause, Pradeep Ravikumar, Jeff Bilmes and Stefanie Jegelka. [videos]
- NIPS 2010 Workshop on Discrete Optimization in Machine Learning: Structures, Algorithms and Applications organized by Andreas Krause, Pradeep Ravikumar, Jeff Bilmes and Stefanie Jegelka. [videos]
- NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity and Polyhedra organized by Andreas Krause, Pradeep Ravikumar and Jeff Bilmes
Software and Materials
- MATLAB Toolbox for submodular function optimization [link] maintained by Andreas Krause.
Journal of Machine Learning Research Open Source Software paper [pdf]
- Class on Submodular Functions by Jeff Bilmes
This page is maintained by Andreas Krause and Carlos Guestrin. Please
send suggested additions or corrections by email.
