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

By D. Golovin, Andreas Krause. Journal of Artificial Intelligence Research, 2010

663 citations recorded by the source corpus.

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 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 applications including sensor placement, 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/52f3960fa991a3b9a0a750bd2740f3dade369011

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Learning to Optimize via Information-Directed Sampling (2014, background): “Another recent line of work [14] shows that information gain based objectives sometimes satisfy a decreasing returns property known as adaptive sub-modularity, implying the greedy policy is competitive with the optimal policy.”
Adaptive Information Gathering via Imitation Learning (2017, background): “…the hidden world map φ , it is not straight forward to apply the approaches discussed in Section II-B - methods have to reason about how P ( φ | { v i } t − 1 i =1 , { y i } t − 1 i =1 ) will evolve. utility However, we assume the function F has an additional property of adaptive submodularity [9].”
Active Learning for Convolutional Neural Networks: A Core-Set Approach (2017, methodology): “Even in the algorithm agnostic case, one can design a set-cover algorithm to cover the hypothesis space using sub-modularity (Guillory & Bilmes, 2010; Golovin & Krause, 2011).”
Teaching Multiple Concepts to a Forgetful Learner (2018, methodology): “2d, we show the performance plot for a fixed teaching horizon of T = 60 when we vary the number of concepts n ∈ [10, 30].”
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age (2016, neutral): “Examples of this kind of effort is the use of submodularity [94] in the related field of active sensors”
Submodular Function Maximization (2014, background): “In this section, we will review the notion of adaptive submodularity (Golovin and Krause, 2011b), a recent generalization of submodularity to adaptive optimization, that allows to develop eﬃcient, provably near-optimal policies to an interesting class of adaptive optimization problems.”
Nonmyopic View Planning for Active Object Classification and Pose Estimation (2014, background): “Unfortunately, Krause [22, Prop.”
Teaching Multiple Concepts to Forgetful Learners (2018, methodology): “2d, we show the performance plot for a fixed teaching horizon of T = 60 when we vary the number of concepts n ∈ [10, 30].”
Active Preference-Based Learning of Reward Functions (2017, background): “It is also adaptive monotone; thus, the results of [10] imply that greedy volume removal for l steps in expectation removes at least (1 − exp(−l/k))OPTk where OPTk is the best solution any adaptive strategy can achieve after k steps.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “– Beyond submodular minimization or maximization: concepts related to submodularity may also be used for sequential decision problems, in particular through the development of adaptive submodularity (see [81] and references therein).”
Lazier Than Lazy Greedy (2014, methodology): “As a result, it has been used as the state-of-the-art implementation in numerous applications including network monitoring (Leskovec et al. 2007), network inference (Rodriguez, Leskovec, and Krause 2012), document summarization (Lin and Bilmes 2011), and speech data subset selection (Wei et al. 2013”
Submodular Maximization in Clean Linear Time (2020, background): “Submodular functions have attracted significant interest from the machine learning community, and have led to the development of algorithms with near-optimal solutions for a wide range of applications, including outbreak detection [52], graph cuts in computer vision [40], image and video summarizati”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, background): “…summarization [Lin and Bilmes, 2011], speech subset selection [Wei et al., 2013] inﬂuence maximization in social networks [Kempe et al., 2003], information gathering [Golovin and Krause, 2011], and graph-cut based image segmentation [Boykov et al., 2001, Jegelka and Bilmes, 2011], to name a few.”