Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity
Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity
复制标题
具有最佳逼近、适应性和查询复杂性的子模最大化
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Morteza Zadimoghaddam
中科院分区：
文献类型：
--
作者：
Matthew Fahrbach;V. Mirrokni;Morteza Zadimoghaddam
次模优化对组合优化中的许多经典问题进行了推广，最近在机器学习（如特征工程和主动学习）中得到了广泛的应用。对于许多大规模优化问题，我们经常关注算法的自适应复杂度，它量化了可以并行执行多个多项式独立函数求值的连续轮数。虽然低自适应是理想的，但它不足以使分布式算法高效，因为在许多子模块优化的实际应用中，函数求值的数量变得非常昂贵。在这些应用的激励下，我们研究了自适应子模块优化的自适应性和查询复杂度。
我们的主要结果是一种分布式算法，用于最大化具有基数约束$k$的单调子模函数，该函数在期望上达到$(1-1/e-\varepsilon)$ -近似。该算法以$O(\log(n))$自适应轮运行，并期望对函数求值oracle进行$O(n)$调用。逼近保证和查询复杂度是最优的，自适应是接近最优的。此外，查询的数量大大少于以前的工作。最后，我们将我们的结果扩展到子模覆盖问题，以证明我们的算法和技术的通用性。
Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization.
Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation. This algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. Last, we extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.
DOI：
10.1137/1.9781611975482.19
发表时间：
2018-04
期刊：
--
影响因子：
--
作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
通讯作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
DOI：
--
发表时间：
2015-02
期刊：
ArXiv
影响因子：
--
作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward
通讯作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward