The adaptive complexity of maximizing a submodular function
The adaptive complexity of maximizing a submodular function
复制标题
DOI：
10.1145/3188745.3188752
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Eric Balkanski;Yaron Singer
中科院分区：
文献类型：
--
作者：
Eric Balkanski;Yaron Singer
本文研究了子模优化的自适应复杂性。非正式地说，问题的自适应复杂性是当多个查询可以在每一轮并行执行时，实现恒定因子近似所需的最小顺序轮数。适应性是计算机科学中广泛研究的一个基本概念，这在很大程度上是因为需要并行计算。有些令人惊讶的是，对子模块优化中的适应性知之甚少。对于在基数约束下最大化单调子模函数的典型问题，就我们所知，到目前为止，所有已知的自适应复杂性介于1和Ω(N)之间。本文的主要结果是一个紧性刻划，证明了在基数约束下最大化一个单调子模函数的自适应复杂性是Θ(Logn)：-我们描述了一个算法，它需要O(Logn)个连续轮次，并且得到一个任意接近1/3的逼近；-我们证明没有任何算法能以少于O(logn/logn)个轮次达到比O(1/logn)更好的逼近。因此，当允许并行化时，我们的算法实现了恒定因子近似，其速度比任何已知的子模最大化算法都快得多。重要的是，近似算法是通过自适应采样实现的，它补充了最近在优化从数据学习的函数方面所做的工作。在许多情况下，我们不知道我们优化的函数，也不知道从标记的样本中学习它们。最近的结果表明，没有一种算法可以像PAC和PMAC模型那样，使用来自任何分布的多个标记样本来获得恒定因子近似保证。由于在任何分布上使用非自适应样本学习都会导致完全不可能的，因此我们认为使用自适应样本学习，即学习者在每一轮中从她选择的分布中获得多(N)个样本。我们的结果表明，在可实现的情况下，存在一个真正的潜在函数来生成数据，Θ(Logn)批自适应样本对于在基数约束下近似地“学习优化”单调子模函数是必要的且充分的。
In this paper we study the adaptive complexity of submodular optimization. Informally, the adaptive complexity of a problem is the minimal number of sequential rounds required to achieve a constant factor approximation when polynomially-many queries can be executed in parallel at each round. Adaptivity is a fundamental concept that is heavily studied in computer science, largely due to the need for parallelizing computation. Somewhat surprisingly, very little is known about adaptivity in submodular optimization. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, to the best of our knowledge, all that is known to date is that the adaptive complexity is between 1 and Ω(n). Our main result in this paper is a tight characterization showing that the adaptive complexity of maximizing a monotone submodular function under a cardinality constraint is Θ(log n): - We describe an algorithm which requires O(log n) sequential rounds and achieves an approximation that is arbitrarily close to 1/3; - We show that no algorithm can achieve an approximation better than O(1 / log n) with fewer than O(log n / log log n) rounds. Thus, when allowing for parallelization, our algorithm achieves a constant factor approximation exponentially faster than any known existing algorithm for submodular maximization. Importantly, the approximation algorithm is achieved via adaptive sampling and complements a recent line of work on optimization of functions learned from data. In many cases we do not know the functions we optimize and learn them from labeled samples. Recent results show that no algorithm can obtain a constant factor approximation guarantee using polynomially-many labeled samples as in the PAC and PMAC models, drawn from any distribution. Since learning with non-adaptive samples over any distribution results in a sharp impossibility, we consider learning with adaptive samples where the learner obtains poly(n) samples drawn from a distribution of her choice in every round. Our result implies that in the realizable case, where there is a true underlying function generating the data, Θ(log n) batches of adaptive samples are necessary and sufficient to approximately “learn to optimize” a monotone submodular function under a cardinality constraint.