Timezone: »

Adaptive Stochastic Optimization: From Sets to Paths
Zhan Wei Lim · David Hsu · Wee Sun Lee

Thu Dec 10 08:00 AM -- 12:00 PM (PST) @ 210 C #69 #None

Adaptive stochastic optimization optimizes an objective function adaptively under uncertainty. Adaptive stochastic optimization plays a crucial role in planning and learning under uncertainty, but is, unfortunately, computationally intractable in general. This paper introduces two conditions on the objective function, the marginal likelihood rate bound and the marginal likelihood bound, which enable efficient approximate solution of adaptive stochastic optimization. Several interesting classes of functions satisfy these conditions naturally, e.g., the version space reduction function for hypothesis learning. We describe Recursive Adaptive Coverage (RAC), a new adaptive stochastic optimization algorithm that exploits these conditions, and apply it to two planning tasks under uncertainty. In constrast to the earlier submodular optimization approach, our algorithm applies to adaptive stochastic optimization algorithm over both sets and paths.

Author Information

Zhan Wei Lim (NUS)
David Hsu (National University of Singapore)
Wee Sun Lee (National University of Singapore)

More from the Same Authors