A Caltech Library Service

Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization

Golovin, Daniel and Krause, Andreas (2011) Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization. Journal of Artificial Intelligence Research, 42 . pp. 427-486. ISSN 1076-9757.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Many problems in artificial intelligence require adaptively making a sequence of decisions with uncertain outcomes under partial observability. Solving such stochastic optimization problems is a fundamental but notoriously difficult challenge. In this paper, we introduce the concept of adaptive submodularity, generalizing 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. In addition to providing performance guarantees for both stochastic maximization and coverage, adaptive submodularity can be exploited to drastically speed up the greedy algorithm by using lazy evaluations. We illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse AI applications including management of sensing resources, viral marketing and active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases, improve approximation guarantees and handle natural generalizations.

Item Type:Article
Related URLs:
URLURL TypeDescription
Krause, Andreas0000-0001-7260-9673
Additional Information:© 2011 AI Access Foundation. Submitted 1/11; published 11/11. An extended abstract of this work appeared in COLT 2010 (Golovin & Krause, 2010). We wish to thank the anonymous referees for their helpful suggestions. This research was partially supported by ONR grant N00014-09-1-1044, NSF grant CNS-0932392, NSF grant IIS-0953413, DARPA MSEE grant FA8650-11-1-7156, a gift by Microsoft Corporation, an Okawa Foundation Research Grant, and by the Caltech Center for the Mathematics of Information.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-09-1-1044
DARPA MSEEFA8650-11-1-7156
Microsoft CorporationUNSPECIFIED
Okawa Foundation Research GrantUNSPECIFIED
Caltech Center for Mathematics of InformationUNSPECIFIED
Record Number:CaltechAUTHORS:20120104-101318653
Persistent URL:
Official Citation:D. Golovin and A. Krause (2011) "Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization", Volume 42, pages 427-486
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28643
Deposited By: Ruth Sustaita
Deposited On:04 Jan 2012 19:38
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page