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

Daniel Golovin; Andreas Krause

Source-linked AI summary

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

Daniel Golovin, Andreas Krause

arXiv:1003.3967v5Mar 21, 2010cs.LGcs.AIcs.DS

TL;DR

Partially observable stochastic optimization requires adaptive decisions under uncertain outcomes, but optimal policy computation is notoriously difficult. The paper introduces adaptive submodularity, proves near-optimality guarantees for adaptive greedy policies, and shows applications including active learning, viral marketing, and sensor placement. It also shows that lazy evaluations can accelerate adaptive greedy optimization and that the framework recovers or generalizes existing application results.

Problem
Partially observable stochastic optimization requires sequential decisions based on uncertain observations, while finding optimal policies is notoriously intractable.
Method
The paper generalizes submodular diminishing returns to adaptive policies through adaptive submodularity and analyzes adaptive greedy algorithms, including lazy evaluations.
Results
Problems satisfying adaptive submodularity admit near-optimal adaptive greedy solutions, with applications to stochastic optimization, viral marketing, and active learning.
Takeaways & Limitations
Adaptive submodularity provides a general framework that recovers known results, proves natural generalizations, and yields performance guarantees for adaptive optimization problems.
Takeaways & Limitations
Robust algorithms for incorrect prior distributions remain an open problem, although the paper briefly discusses robustness guarantees.

Abstract

from arXiv · show

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.

1. Introduction

The paper introduces adaptive submodularity for partially observable stochastic optimization, where optimal policy computation is generally intractable. It establishes greedy guarantees and applies the framework to several adaptive optimization and learning problems.

Motivation: Partially observable stochastic optimization requires sequential decisions conditioned on uncertain observations, while finding optimal policies is generally intractable.The paper targets classes where simple methods can still achieve near-optimal performance.
Core concept: Adaptive submodularity generalizes diminishing returns from set functions to policies whose actions depend on observations.For deterministic distributions, it reduces to classical submodularity.
Guarantees: If a problem satisfies adaptive submodularity, a simple adaptive greedy policy obtains near-optimal solutions for stochastic maximization, coverage, and a natural min-sum objective.The paper also states that no polynomial-time algorithm can generally obtain better solutions under reasonable complexity-theoretic assumptions.
Algorithms: Adaptive submodularity supports accelerated greedy optimization through lazy evaluations and enables data-dependent bounds on the optimum.These benefits extend practical advantages previously associated with classical submodular optimization.
Applications: Applications include stochastic coverage, viral marketing, sensor placement, and active learning, where the framework recovers known results and proves natural generalizations.In active learning, reduction in version-space probability mass is adaptive submodular, yielding a near-optimal querying policy.
Paper scope: The paper studies adaptive stochastic optimization through formal definitions, theoretical guarantees, applications, empirical sensor-selection results, and hardness results.Its application sections cover stochastic maximization, stochastic coverage, viral marketing, and active learning.

2. Adaptive Stochastic Optimization

The paper models adaptive optimization as sequential item selection under uncertain realizations and partial observations. Policies use observed states to choose actions, optimizing expected utility, coverage cost, or time-to-utility objectives.

Items and realizations: Items have initially unknown states drawn from a known prior distribution, and sequential observations update the partial realization of selected items.The Bayesian model supports posterior reasoning about unselected items.
Policies: Partial realizations encode actions and observations and determine posterior beliefs about the states of items not yet selected.This makes them analogous to belief states in partially observable Markov decision processes.
Policies: A policy maps partial realizations to the next item, so its decisions can adapt to observations and can be represented as a decision tree.Randomized policies instead map partial realizations to distributions over items.
Objectives: The adaptive stochastic maximization objective maximizes expected utility subject to constraints, with utility depending on selected items and their realized states.A typical constraint is a budget k on the number of selected items.
Objectives: Minimum-cost cover seeks a policy that achieves quota Q under every realization while minimizing expected or worst-case item count.Worst-case cost equals the maximum number of selected items and the depth of the deepest decision-tree leaf.
Objectives: The framework also considers min-sum cover, which minimizes the accumulated expected shortfall between target utility and utility obtained over time.The paper focuses on unit item costs while describing extensions to non-uniform costs in the Appendix.
Complexity: Even linear utility functions yield hard-to-approximate versions of the adaptive stochastic optimization, coverage, and min-sum problems.The paper nevertheless identifies sufficient conditions for approximate solution methods.

3. Adaptive Submodularity

This section moves from classical submodularity to adaptive planning, where policies choose items based on observations. It defines adaptive marginal benefit, monotonicity, and submodularity for uncertain item states.

Classical submodularity: Classical monotone submodular maximization under a cardinality constraint gives greedy solutions at least a (1 −1/e) fraction of the optimum.This guarantee is tight under the stated complexity assumption.
From non-adaptive to adaptive: Adaptive planning uses policies rather than subsets because each action can depend on information revealed by earlier selections.The paper represents adaptive strategies as decision trees or conditional plans.
Adaptive definitions: Adaptive marginal benefit is the conditional expected increase from selecting an item after observing a partial realization.The expectation is taken over the posterior distribution of item states consistent with the observations.
Adaptive definitions: Adaptive monotonicity requires every item's conditional expected marginal benefit to be nonnegative.The paper also notes closure properties for nonnegative combinations of adaptive monotone submodular functions.
Adaptive definitions: Adaptive submodularity requires conditional expected marginal benefit to decrease as more items are selected and their states are observed.The condition is defined relative to the distribution over realizations and reduces to classical submodularity for deterministic distributions.

4. The Adaptive Greedy Policy

The adaptive greedy policy repeatedly selects the item with the largest expected marginal benefit given current observations. The paper also develops approximate, cost-aware, and lazy-evaluation variants.

Greedy selection: At each iteration, adaptive greedy selects the item maximizing expected marginal benefit conditioned on the states observed so far.The policy then observes the selected item's state before making the next choice.
Cost handling: Non-uniform costs can be handled by replacing the selection rule with an expected benefit-to-cost ratio.The main discussion focuses on the uniform-cost case.
Approximate greedy: An α-approximate greedy policy selects an item whose expected marginal benefit is within a multiplicative α factor of the best available item.The paper connects this robustness to multiplicative errors from incorrect priors.
Acceleration: Lazy evaluations exploit adaptive submodularity to avoid recomputing every marginal benefit while preserving the greedy policy's selections.The accelerated implementation maintains previously computed marginal-benefit priorities and reevaluates items as needed.
Acceleration: 4 to 40: accelerated adaptive greedy achieved speedup factors in this range on two sensor-selection problems.The comparison was between naive and accelerated implementations.

5. Guarantees for the Greedy Policy

Under adaptive monotonicity and adaptive submodularity, greedy policies inherit classic greedy guarantees for maximization, coverage, and min-sum coverage. The framework also supports data-dependent bounds and specialized coverage results.

General guarantees: Adaptive greedy inherits the classic performance guarantees for maximum coverage, minimum set cover, and min-sum submodular coverage.The result extends to α-approximate greedy policies and focuses on unit costs, with non-uniform costs handled by benefit-to-cost ratios.
Stochastic maximization: (1 −1/e): with k steps, greedy achieves at least this fraction of the expected value of the optimal adaptive policy.This is the α = 1, ℓ = k specialization of the general theorem.
Data-dependent bounds: Data-dependent bounds can provide tighter estimates of the gap to optimum than problem-independent greedy guarantees.The bounds are computable from marginal benefits and apply to any current set, not only greedy-selected sets.
Min-sum coverage: For adaptive stochastic min-sum cover, an α-approximate greedy policy satisfies cΣ(π) ≤4α cΣ(π∗).This extends non-adaptive min-sum submodular cover results to adaptive policies in the unit-cost setting.

6. Application: Stochastic Submodular Maximization

The paper extends stochastic submodular maximization to unreliable sensors whose states are revealed adaptively. Under independent sensor states and monotone submodular utility, adaptive greedy achieves a near-optimal solution.

Problem: The problem models sensor deployments whose states, including failures or varying sensing quality, are unknown before placement.Each location e has a state φ(e), and utility depends on the selected locations and their realized states.
Model and analysis: Independent sensor states make the expected utility amenable to adaptive-submodularity analysis.The prior factors across locations, enabling the paper to show diminishing expected marginal returns as observations accumulate.
Results: The paper extends prior stochastic submodular maximization results from complete sensor failure or success to multiple types of failures.It proves f(A, φ) is adaptive submodular under the independent-state prior and invokes the general greedy guarantee.
Results: Theorem 16 gives an approximation guarantee for any α-approximate greedy policy over ℓ selections, with the greedy case obtained by setting α = 1 and ℓ = k.The supplied theorem statement introduces the independent prior, monotone submodular objective, and comparison with any policy.

7. Application: Stochastic Submodular Coverage

The paper studies adaptive coverage when randomly realized sensor or item outcomes must reach a utility quota at minimum cost. Its framework yields guarantees for stochastic submodular coverage, including a logarithmic-squared approximation for stochastic set coverage.

Problem: Stochastic Submodular Coverage minimizes the number or cost of unreliable sensor placements needed to achieve a prescribed utility quota.The model assumes independent sensor states and requires that sufficiently many placements can attain the quota in every realization.
Stochastic Set Coverage: Stochastic Set Coverage represents each item as a distribution over subsets of a ground set U, with independent sampled sets revealed when items are selected.The objective counts the elements covered by the sampled sets, and the quota is set to n = |U|.
Results: The framework generalizes earlier stochastic set-coverage analyses to richer item distributions over subsets of U.The paper identifies the guarantee as a corollary of Theorem 17.
Results: (ln(n) + 1)^2-approximation is achieved by adaptive greedy for Stochastic Set Coverage, where n := |U| is the ground-set size.This result allows arbitrarily many outcomes for each stochastic set.
Proof strategy: The analysis applies the general coverage theorem after establishing strong adaptive monotonicity, strong adaptive submodularity, and self-certification.Pointwise submodularity supports the strong adaptive-submodularity condition, while a common full-realization quota yields self-certification.

8. Application: Adaptive Viral Marketing

The paper applies adaptive submodularity to viral marketing, where promotions spread stochastically through social networks and decisions can incorporate observed diffusion. It establishes greedy-policy guarantees for broader reward and coverage objectives under specified feedback models.

Problem: Adaptive viral marketing selects promotional recipients sequentially, observes resulting demand spread, and adapts later choices.The adaptive analogue replaces a fixed seed set with decisions informed by observed diffusion.
Guarantees: The greedy policy obtains guarantees for influencing people under adaptive viral marketing, including arbitrary nonnegative monotone submodular rewards.This generalizes cardinality and weighted influence objectives to rewards that can encode diversity across demographic segments.
Coverage: For adaptive viral marketing, the paper also treats minimum-cost cover and reports a squared logarithmic approximation for the greedy policy.The paper presents this as an approximation result for the adaptive variant.
Feedback model: Under independent cascades, activating a person reveals state information about the broader social network rather than only that individual.The item state is modeled as a function of the network-wide diffusion state.
Guarantees: The analysis covers independent-cascade and full-adoption feedback models for rewards defined as monotone submodular functions of activated nodes.The objective is f(S, φ) = ˆf(σ(S, φ)), where σ denotes all activated nodes.

9. Application: Automated Diagnosis and Active Learning

The paper models diagnosis and active learning as adaptive querying to identify a target hypothesis by shrinking the version space. It proves adaptive-submodular structure and derives query-complexity guarantees for generalized binary search under uniform and arbitrary priors.

Applications: Automated diagnosis adaptively selects tests to infer a patient’s state, while active learning selects informative labels to reduce expert-labeling costs.In both settings, observations eliminate hypotheses inconsistent with the accumulated evidence.
Generalized binary search: Generalized binary search selects queries that myopically shrink a measure of version-space size or probability mass.The Bayesian version uses a prior over hypotheses and obtains an O(log 1/min_h pH(h))-approximation for expected queries.
Adaptive submodularity: The reduction in version-space mass is adaptive submodular, enabling a new analysis of generalized binary search that is more amenable to extensions and generalizations.The paper notes that this guarantee is weaker than the optimal previous analysis.
Uniform prior: Under a uniform prior, generalized binary search uses at most OPT (ln (|H| −1) + 1)^2 queries in expectation.The reduction treats hypothesis identification as an Adaptive Stochastic Min Cost Cover instance with Q = 1−1/|H| and η = 1/|H|.
Arbitrary priors: For arbitrary priors, the analysis gives an upper bound of OPT (ln (1/min_h pH(h)) + 1)^2 queries for generalized binary search.The objective is shown to be strongly adaptive monotone and strongly adaptive submodular under arbitrary priors.

10. Experiments

The experiments evaluate adaptive greedy sensor selection for entropy reduction when sensors may fail. They compare standard and lazy-evaluation implementations and examine data-dependent bounds on optimal expected reward.

Sensor selection: The sensor-selection experiments adaptively maximize expected Shannon-entropy reduction while observing whether each selected sensor fails.The application models correlated temperature or traffic measurements and unreliable sensors.
Objective: The objective g(A) = I(XV; YA) is monotone submodular when observations are conditionally independent given the latent variables.This supports the adaptive-submodular formulation used for unreliable sensor selection.
Datasets: The evaluation uses temperature data from 46 sensors and traffic-speed data from highway sensors.The temperature measurements were sampled every 30 seconds for five consecutive days, while traffic data covered weekday morning periods for one month.
Lazy evaluations: At a 50% sensor-failure rate, the study compares execution time and function-evaluation counts for naive and lazy adaptive greedy algorithms.The accelerated algorithm can avoid extra evaluations after selecting a sensor that fails, unlike naive greedy.
Data-dependent bounds: Data-dependent bounds can tighten with later observations when the reward has strong diminishing returns, whereas β0 is best when g is modular.The paper cautions that taking the minimum of random bounds is not generally valid without additional concentration control.

11. Adaptivity Gap

The paper studies how much adaptive policies can outperform non-adaptive policies through the adaptivity gap. In an active-learning threshold problem, non-adaptive identification costs Ω(n), while binary search costs O(log n).

Definition: The adaptivity gap is the worst-case ratio between optimal adaptive and optimal non-adaptive performance over problem instances.For minimum-cover objectives, the ratio is expressed using expected non-adaptive cost divided by expected adaptive cost.
Lower bound: Even for adaptive submodular functions, Adaptive Stochastic Min-Sum Cover has adaptivity gap Ω(n/log n).Here n = |E|.
Non-adaptive policy: In the threshold active-learning construction, an optimal non-adaptive policy has expected cost Ω(n).Its probability of identifying the correct hypothesis within n/4 steps is at most 1/2, yielding an expected-cost lower bound of n/8.
Adaptive policy: A natural adaptive binary-search policy identifies the threshold in O(log n) steps.This adaptive strategy establishes the stated adaptivity-gap lower bound.

12. Hardness of Approximation

Without adaptive submodularity, adaptive stochastic optimization can be extremely hard to approximate, even for pointwise modular objectives. The paper establishes strong conditional hardness results for maximization, minimum-cost coverage, and min-sum cover.

Without adaptive submodularity, problems (1), (2), and (3) lack O(|E|^(1−ε)) approximation guarantees unless the polynomial hierarchy collapses to ΣP_2.This inapproximability holds even when the objective is pointwise modular.
O(|E|^(1−ε/β)) hardness holds for adaptive stochastic maximization with a budget of βk items against an optimal policy using k items.The result applies for all β ≥ 1 and assumes PH ≠ ΣP_2.
The hardness construction shows that an optimal policy can cover every realization with k = O(|E|^(ε/2)) items, while randomized polynomial-time algorithms may require a much larger budget.To ensure reward ratio one, the required budget factor can be β = Ω(|E|^(1−ε)).
O(|E|^(1−ε)) hardness holds for adaptive stochastic minimum-cost coverage and adaptive stochastic min-sum cover.Both results hold even for pointwise modular objectives, under the stated complexity-theoretic assumption.

13. Related Work

The paper situates adaptive submodularity among stochastic, online, active-learning, depletion, recourse, Bayesian optimization, and POMDP approaches. Its distinctive aim is a general problem structure that unifies adaptive optimization problems and yields guarantees through prior-dependent structure.

Unlike work generalizing individual problems such as Set Cover, Knapsack, or Traveling Salesman, this paper introduces adaptive submodularity as a unifying problem structure.The framework parallels the unifying role of classical submodularity for non-adaptive optimization.
Interactive Submodular Set Cover emphasizes worst-case policy cost, whereas this paper focuses mainly on average-case policy cost and uses a prior-dependent structure.That dependence supports guarantees such as Theorem 13 for self-certifying instances.
Stochastic Depletion also uses greedy algorithms for near-optimal adaptive optimization, but its problems, approaches, and applications differ substantially from this paper’s.The reported similarity is conceptual rather than problem-specific.
Stochastic optimization with recourse reveals information independently of actions, unlike the action-dependent information structure studied here.Recourse problems use multiple stages in which later action costs increase.
Related work includes Bayesian Global Optimization, POMDPs, and subsequent adaptive-submodularity applications in active learning and conservation planning.The cited later results include squared-logarithmic active-learning guarantees and competitiveness guarantees for ecological reserve design.

14. Conclusions

The paper presents adaptive submodularity as a general framework for efficient approximate planning under uncertainty and partial observability. It extends classical greedy guarantees to adaptive policies and supports acceleration and data-dependent analysis.

Adaptive submodularity generalizes submodular set functions to adaptive policies through an adaptive diminishing-returns property.For deterministic distributions, the generalization reduces to classical submodular set functions.
Adaptive greedy policies obtain generalized guarantees for constrained maximization and coverage problems with minimum-cost and minimum-sum objectives.The paper also gives constant-factor or polylogarithmic-factor approximation results for the corresponding well-behaved problems.
Lazy evaluations accelerate adaptive greedy algorithms, while data-dependent bounds provide information about the optimal solution.

15. Additional Proofs and Incorporating Item Costs

The appendix extends the framework to non-uniform item costs, formalizes policy operations and adaptive monotonicity, and proves cost-sensitive greedy and data-dependent guarantees. It also relates pointwise submodularity to strong adaptive submodularity.

Incorporating Item Costs: Non-uniform item costs are incorporated by defining item-cost functions, conditional policy cost, policy concatenation, and several forms of policy truncation.Strict, lax, and randomized truncations describe which partially completed item runs are retained at a time threshold.
Incorporating Item Costs: With costs, greedy selects an item maximizing conditional expected marginal benefit divided by its cost, while approximate greedy achieves at least a 1/α fraction of the best ratio.Approximate greedy terminates when no item has positive expected marginal benefit.
Additional Proofs: Adaptive monotonicity is equivalent to nonnegative conditional expected marginal benefits and to nondecreasing expected value under policy concatenation.The equivalence is established in Lemma 36.
Additional Proofs: The adaptive data-dependent bound with costs upper-bounds a policy’s conditional marginal benefit using its conditional cost and the largest marginal-benefit-to-cost ratio.The bound is derived through a linear program whose value can be computed by a simple greedy algorithm.
Incorporating Item Costs: Theorem 38 extends adaptive greedy approximation guarantees to adaptive monotone submodular objectives with arbitrary integer item costs.
Additional Proofs: If an objective is both adaptive submodular and pointwise submodular, then it is strongly adaptive submodular.

Proof of Theorem 40

The proof bounds adaptive greedy’s expected cost by comparing its per-unit reward price with an alternative charging scheme for an optimal policy. Separate arguments handle the final reward gap in general and self-certifying instances.

Alternative-cost analysis: The execution arborescence organizes partial realizations and edges that span x expected benefit, allowing the analysis to partition realizations and define alternative charges.Sources, targets, and successors of these edges support the expectation calculations.
Alternative-cost analysis: The concatenative pseudopolicy runs π until it is about to reach x expected reward, then executes π∗ from scratch on the same realization.Its selected items are dom(ψ(φ,x)) ∪ E(π∗,φ).
Final-gap analysis: For x near the maximum reward Q, general instances use a final gap δη, whereas self-certifying instances use η because every realization consistent with the current observations remains uncovered.The final selected item must close the corresponding conditional-value gap to Q.
Alternative-cost analysis: The proof bounds alternative costs by sampling random execution traces conditioned on an optimal policy’s partial realization and using adaptive submodularity to control later marginal benefits.For general instances, every positive marginal benefit is at least δη; for self-certifying instances, it is at least η.

PUTTING IT ALL TOGETHER

The final analysis extends the greedy guarantees to arbitrary item costs and worst-case coverage by combining charging arguments with adaptive monotonicity and submodularity. It also establishes a matching logarithmic hardness result for general instances.

Average-cost guarantees: The alternative charging scheme charges greedy according to outcome-dependent reward gains, while preserving expected charge equal to cavg(π).Its instantaneous price is c(e)/∆(e|ψ) per unit expected gain.
Worst-case guarantees: Theorem 48 assumes adaptive monotonicity and adaptive submodularity, an α-approximate cost-greedy policy, and an optimal worst-case policy covering every realization at cost k.The bound uses maximum expected reward Q and parameters η and δ.
Worst-case guarantees: After ℓ=αk ln(Q/δη) greedy steps, appending one final action yields a policy that covers every realization.The proof uses the implication that a residual gap below δη must be zero.
Worst-case guarantees: The resulting worst-case cost is at most ℓ+αk, because the appended final item costs at most αk under approximate cost-greedy selection.The optimal worst-case policy’s cost bound controls the marginal-benefit-per-cost comparison.
Worst-case guarantees: Adaptive monotonicity implies that completing any policy with all remaining items cannot reduce conditional expected value, yielding the comparison needed for the worst-case proof.Lemma 49 formalizes this by augmenting a policy and then selecting all remaining items.
Hardness: No polynomial-time (1−ϵ) ln(Q/δη)-approximation exists for general Adaptive Stochastic Min Cost Cover under the stated complexity assumption, for either average-case or worst-case objectives.The result follows by reduction from Set Cover.

15.5 The Min-Sum Objective

The min-sum objective measures cumulative cost until coverage, and approximate adaptive greedy achieves a 4α approximation. A constructed treasure-hunting instance shows that without adaptive submodularity, polynomial-time algorithms can perform arbitrarily poorly relative to an unconstrained optimal policy.

Min-sum objective: The arbitrary-cost min-sum objective uses strict truncation π[←t] to measure cumulative cost over execution progress.The analysis extends the unit-cost definition to items with arbitrary costs.
Approximation guarantee: Any α-approximate greedy policy achieves cΣ(π) ≤ 4α cΣ(π∗) for every policy π∗.The proof uses a lemma relating greedy progress to the residual value of arbitrary policies.
Approximation guarantee: The proof compares residual rewards across truncation levels using a geometric argument, with adaptive monotonicity and submodularity making the relevant residual sequence non-increasing.Figure 6 illustrates the inequality used in this comparison.
Hardness without adaptive submodularity: The hardness construction uses treasure locations, secret-shared maps, and a puzzle identifying the unique correct map, creating synergistic item effects.Partial queries to a map reveal nothing about the treasure location, while an unconstrained policy can solve the puzzle and decode the map.
Hardness without adaptive submodularity: The computationally unconstrained policy obtains reward one with budget k=n3+s+1 by sampling the puzzle, correct map, and treasure location.The construction’s item types are treasure bits, map bits, and puzzle bits.
Hardness without adaptive submodularity: Under the stated complexity assumption, polynomial-time randomized algorithms with budget βk achieve at most o(β/|E|^(1−ε)) of the optimal value, yielding approximation ratio ω(|E|^(1−ε)/β).The construction sets |E|=n^(3+1/γ)(1+o(1)) and chooses γ≤ε/6.