WNCG Seminar Series

Friday, November 13, 2015
11:00am - 12:00pm
UTA 7.532

Abstract: Submodular functions capture a wide spectrum of discrete problems in machine learning, signal processing and computer vision. They are characterized by intuitive notions of diminishing returns and economies of scale, and often lead to practical algorithms with theoretical guarantees.

In the first part of this talk, I will give a general introduction to the concept of submodular functions, their optimization and example applications in machine learning.

In the second part, I will demonstrate how the close connection of submodularity to convexity leads to fast algorithms for minimizing a subclass of submodular functions - those decomposing as a sum of submodular functions. Using a specific relaxation, the algorithms solve the discrete submodular optimization problem as a "best approximation" problem. They are easy to use and parallelize, and solve both the convex relaxation and the original discrete problem. Their convergence analysis combines elements of geometry and spectral graph theory.

This is joint work with Robert Nishihara, Francis Bach, Suvrit Sra and Michael I. Jordan.

Watch the full talk on the WNCG YouTube Channel:

Watch Part 1 Here

Watch Part 2 Here


Assistant Professor
Massachusetts Institute of Technology

Stefanie Jegelka is a postdoc at UC Berkeley, working with Michael Jordan and Trevor Darrell. She is a member of the AMPlab and a visitor at the International Computer Science Institute. In 2015, she will join the EECS Department at MIT as an assistant professor.

Before joining Berkeley, Dr. Jegelka completed her PhD in Bernhard Schölkopf's group at the Max Planck Institutes in Tübingen and graduated from ETH Zurich. During her PhD, she worked with Jeff Bilmes, and before that with Ulrike von Luxburg and Arthur Gretton.

Her research focuses on combinatorial problems in Machine Learning, in particular how to exploit nice mathematical structure for new models and efficient algorithms. Her research interests include submodularity and discrete optimization, graph problems, graphical models, kernel methods and clustering, distributed machine learning, and applications e.g. in computer vision and biology.