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

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

2010-03-21

arxiv.org/abs/1003.3967v3

Computer Science

Learning

46 pages, 6 figures. Version 3 is a major revision, with an improved policy-centric exposition and much new material

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-316429