Events Calendar

CS Colloquium

Speaker: Dr. Daniel Golovin , Cal Tech

Talk Title: Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization

Abstract: Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this talk, I will introduce a new concept called adaptive submodularity, which generalizes submodular set functions to adaptive policies. In many respects adaptive submodularity plays the same role for adaptive problems as submodularity plays for nonadaptive problems. Specifically, just as many nonadaptive problems with submodular objectives have efficient algorithms with good approximation guarantees, so too do adaptive problems with adaptive submodular objectives. We use this fact to recover and generalize several previous results in adaptive optimization, including results for active learning and adaptive variants of maximum coverage and set cover. Applications include machine diagnosis, observation selection and sensor placement problems, and an adaptive version of a viral marketing problem studied by Kempe et al. Joint work with Andreas Krause.

Biography: Daniel Golovin is a postdoctoral fellow in Caltech's Center for the Mathematics of Information. His current research mainly focuses on online and approximation algorithms for machine learning and optimization, with an eye towards creating principled solutions that work well in practice. Prior to joining Caltech, he obtained a PhD from Carnegie Mellon University in 2008, and spent an additional year there at the Center for Computational Thinking. He did his undergraduate work at Cornell University.

Host: Dr. David Kempe

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Kanak Agrawal