Congratulations to professor Jeff Bilmes, Rishabh Iyer and Steffi Jegelka for winning the best paper award at the 2013 International Conference on Machine Learning (ICML)! Their award-winning titled, “Fast Semidifferential-based Submodular Function Optimization” was presented at the 30th annual ICML in Atlanta, GA on June 19th. Rishabh is a current EE graduate student advised by Jeff Bilmes, and Steffi is a former student of Jeff Bilmes now working as a postdoc at UC Berkeley.
Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes; JMLR W&CP 28 (3): 855–863, 2013
We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization. Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular minimization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning. We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments.