An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
复制标题
DOI：
10.1137/1.9781611975482.19
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
中科院分区：
文献类型：
--
作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
在本文中，我们研究了亚物种最大化的适应性。自适应性量化算法可以并行执行函数评估时进行的顺序回合数。适应性是一个基本概念，在计算机科学领域的各个领域进行了大量研究，这在很大程度上是由于需要并行计算。对于在基数限制下最大化单调下一个函数的规范问题，众所周知，一种简单的贪婪算法实现了$ 1-1/e $ $的近似值，并且此近似值对于多项式时间算法是最佳的。令人惊讶的是，尽管为大规模数据集进行了大规模的实次优化努力，直到最近，还没有已知的算法来实现此问题的恒定因子近似值，该问题的适应性在地面的大小上是$ n $。 Balkanski and Singer的最新工作描述了一种算法，该算法在$ \ Mathcal {o}中任意接近$ 1/3 $ $ 1/3 $}（\ log n）$自适应回合，并表明没有算法可以在$ \ tilde中获得恒定的因子近似值{o}（\ log n）$自适应回合。这种方法在适应性（和平行运行时间）方面达到了指数加速，而付出了近似质量。在本文中，我们描述了一种新的方法，该方法得出了一种算法，该算法的近似值与$ \ Mathcal {o}（\ log n）$自适应回合的最佳$ 1-1/e $保证。因此，该算法在并行运行时间以近似质量的任意损失为代价时达到了指数加速。此保证在近似和适应性方面都是最佳的，最多可达低阶项。
In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily studied across a variety of areas in computer science, largely due to the need for parallelizing computation. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, it is well known that a simple greedy algorithm achieves a $1-1/e$ approximation and that this approximation is optimal for polynomial-time algorithms. Somewhat surprisingly, despite extensive efforts on submodular optimization for large-scale datasets, until very recently there was no known algorithm that achieves a constant factor approximation for this problem whose adaptivity is sublinear in the size of the ground set $n$. Recent work by Balkanski and Singer describes an algorithm that obtains an approximation arbitrarily close to $1/3$ in $\mathcal{O}(\log n)$ adaptive rounds and shows that no algorithm can obtain a constant factor approximation in $\tilde{o}(\log n)$ adaptive rounds. This approach achieves an exponential speedup in adaptivity (and parallel running time) at the expense of approximation quality. In this paper we describe a novel approach that yields an algorithm whose approximation is arbitrarily close to the optimal $1-1/e$ guarantee in $\mathcal{O}(\log n)$ adaptive rounds. This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. This guarantee is optimal in both approximation and adaptivity, up to lower order terms.