February 15, 2019
12:00 PM - 1:00 PM
Title: Submodular Optimization: From Discrete to Continuous and Back
Abstract: The difficulty of searching through a massive amount of data in order to quickly make an informed decision is one of today’s most ubiquitous challenges. Many scientific and engineering models feature inherently discrete decision variables—from phrases in a corpus to objects in an image. The study of how to make near-optimal decisions from a massive pool of possibilities is at the heart of combinatorial optimization. Many of these problems are notoriously hard, and even those that are theoretically tractable may not scale to large instances. However, the problems of practical interest are often much more well-behaved and possess extra structures that allow them to be amenable to exact or approximate optimization techniques. Just as convexity has been a celebrated and well-studied condition under which continuous optimization is tractable, submodularity is a condition for which discrete objectives may be optimized.
In order to provide the tightest approximation guarantees for submodular optimization problems, we usually need to leave the space of discrete domains and consider their continuous relaxations. To this end, we will explore the notion of submodularity in the continuous domains and introduce a broad class of non-convex objective functions. Despite the apparent lack of convexity, we will see that first-order optimization methods can provide strong approximation guarantees. We then show that such continuous relaxations can be used as an interface to provide tight approximation guarantees for maximizing stochastic submodular set functions.
I will not assume any particular background on submodularity or optimization and will try to motivate and define all the necessary concepts during the talk.
Bio: Hamed Hassani is currently an assistant professor of Electrical and Systems Engineering department at the University of Pennsylvania. Prior to that, he was a research fellow at Simons Institute for the Theory of Computing (UC Berkeley), and a post-doctoral researcher in the Computer Science department at ETH Zurich. He received a Ph.D. degree in Computer and Communication Sciences from EPFL, Lausanne. Hamed’s fields of interest include coding and information theory, machine learning as well as theory and applications of graphical models. He is the recipient of the 2014 IEEE Information Theory Society Thomas M. Cover Dissertation Award. His co-authored paper at the International Symposium on Information Theory (ISIT) 2015 received the IEEE Jack Keil Wolf ISIT Student Paper Award.