Adaptive submodularity: theory & applications in active learning and stochastic optimization

3rd April 2014

Andreas Krause , assistant professor at Swiss Federal Institute of Technology, Z├╝rich, Switzerland


Solving sequential decision problems under partial observability is a fundamental but notoriously difficult challenge. In this talk, I will introduce the new concept of adaptive submodularity, generalizing the classical notion of submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy. The concept allows to recover, generalize and extend existing results in diverse applications including sensor management, viral marketing and active learning. In this talk, I will focus on two case studies. In an application to Bayesian experimental design, we show how greedy optimization of a novel adaptive submodular criterion outperforms standard myopic techniques based on information gain and value of information. I will also discuss how adaptive submodularity helps to address problems in biodiversity monitoring in the rainforest via conservation drones.