Adaptivity in Adaptive Submodularity
Adaptivity in Adaptive Submodularity
复制标题
DOI：
--
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Hossein Esfandiari;Amin Karbasi;V. Mirrokni
中科院分区：
文献类型：
--
作者：
Hossein Esfandiari;Amin Karbasi;V. Mirrokni
自适应顺序决策是机器学习和人工智能的核心挑战之一。在这样的问题中，目标是设计一种互动政策，该政策计划采取行动，从有限的$ n $行动中，给定一些部分观察。已经表明，在许多应用程序中，例如主动学习，机器人技术，顺序实验设计和主动检测，效用函数满足自适应下调性，这一概念概述了减少对策略的回报的概念。在本文中，我们重新审视适应性在最大化适应性单调下调函数方面的力量。我们提出了一个有效的批处理政策，即使用$ O（\ log n \ times \ log k）$自适应的观测回合可以实现几乎紧密的$（1-1/e- \ epsilon）$近似保证在完全顺序的设置中，这将进行$ k $的操作。为了补充我们的结果，我们还表明，不可能使用$ O（\ log n）$自适应回合实现恒定因子近似。我们还将结果扩展到自适应随机的最低成本覆盖范围，目标是达到最便宜的政策所需的公用事业$ Q $。我们首先证明了戈洛文（Golovin）和克劳斯（Krause）的猜想，即贪婪的政策实现了渐近的对数近似保证，而无需诉诸于更强的适应性概念。然后，我们提出了一个批处理策略，该策略通过类似的信息和平行性方案在Polyogarithmic自适应回合中提供相同的保证。我们的结果缩小了通过指数因素自适应下调最大化的适应性差距。
Adaptive sequential decision making is one of the central challenges in machine learning and artificial intelligence. In such problems, the goal is to design an interactive policy that plans for an action to take, from a finite set of $n$ actions, given some partial observations. It has been shown that in many applications such as active learning, robotics, sequential experimental design, and active detection, the utility function satisfies adaptive submodularity, a notion that generalizes the notion of diminishing returns to policies. In this paper, we revisit the power of adaptivity in maximizing an adaptive monotone submodular function. We propose an efficient batch policy that with $O(\log n \times\log k)$ adaptive rounds of observations can achieve an almost tight $(1-1/e-\epsilon)$ approximation guarantee with respect to an optimal policy that carries out $k$ actions in a fully sequential setting. To complement our results, we also show that it is impossible to achieve a constant factor approximation with $o(\log n)$ adaptive rounds. We also extend our result to the case of adaptive stochastic minimum cost coverage where the goal is to reach a desired utility $Q$ with the cheapest policy. We first prove the conjecture by Golovin and Krause that the greedy policy achieves the asymptotically tight logarithmic approximation guarantee without resorting to stronger notions of adaptivity. We then propose a batch policy that provides the same guarantee in polylogarithmic adaptive rounds through a similar information-parallelism scheme. Our results shrink the adaptivity gap in adaptive submodular maximization by an exponential factor.