Adaptive Submodularity: Theory and Applications in 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 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.

60 pages, 6 figures. Version 5 addresses a flaw in the proof of Theorem 13 identified by Nan and Saligrama (2017). The revision includes a weaker version of Theorem 13, guaranteeing squared logarithmic approximation under an additional strong adaptive submodularity condition. This condition is met by all applications considered in the paper, as discussed in the revised Sections 7, 8 and 9

References in corpus (4)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Near-optimal Nonmyopic Value of Information in Graphical Models
• Adaptive Submodular Optimization under Matroid Constraints
• Average-Case Active Learning with Costs

Cited by in corpus (19)

• Adaptive Influence Maximization in Dynamic Social Networks
• Near-Optimal Bayesian Active Learning with Noisy Observations
• Adaptive Communication Networks with Privacy Guarantees
• Adaptive Influence Maximization: If Influential Node Unwilling to Be the Seed
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Exploiting Submodular Value Functions For Scaling Up Active Perception
• Adaptive Submodular Optimization under Matroid Constraints
• Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization
• Seeding with Costly Network Information
• The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions
• A Tight Bound for Stochastic Submodular Cover
• A k-hop Collaborate Game Model: Extended to Community Budgets and Adaptive Non-Submodularity
• Sequential testing problem: A follow-up review
• Adaptive Region-Based Active Learning
• Flattening a Hierarchical Clustering through Active Learning
• Maximizing Influence with Graph Neural Networks
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Efficient Online Decision Tree Learning with Active Feature Acquisition