Approximation Guarantees for Adaptive Sampling
Approximation Guarantees for Adaptive Sampling
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Eric Balkanski;Yaron Singer
中科院分区：
文献类型：
--
作者：
Eric Balkanski;Yaron Singer
本文分析了一种子模最大化的自适应采样方法。自适应采样是一种最近被证明在基数约束下实现子模最大化的恒因子近似保证的技术，其自适应轮数比以往研究的任何用于该问题的恒因子近似算法都要少得多。适应性量化了当函数求值可以并行执行时算法进行的连续轮数，并且是算法的并行运行时间，最高可达低阶项。自适应采样以牺牲近似性为代价实现了指数级加速。从理论上讲，可以保证得到的解接近最优解的1/3。然而，实验表明，自适应采样技术在实践中取得了更好的价值。在本文中，我们为这一现象提供了理论上的证明。特别地，我们证明了在函数曲率非常温和的条件下，自适应采样技术在保持其低自适应性的同时，实现了任意接近1/2的逼近。此外，我们还证明了逼近比接近于1与子模函数的齐性直接相关。此外，我们还在曲率和均匀属性易于操纵的真实数据集上进行了实验，展示了近似与曲率的关系，以及自适应采样在实践中的有效性。
In this paper we analyze an adaptive sampling approach for submodular maximization. Adaptive sampling is a technique that has recently been shown to achieve a constant factor approximation guarantee for submodular maximization under a cardinality constraint with exponentially fewer adaptive rounds than any previously studied constant factor approximation algorithm for this problem. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel and is the parallel running time of an algorithm, up to low order terms. Adaptive sampling achieves its exponential speedup at the expense of approximation. In theory, it is guaranteed to produce a solution that is a 1/3 approximation to the optimum. Nevertheless, experiments show that adaptive sampling techniques achieve far better values in practice. In this paper we provide theoretical justification for this phenomenon. In particular, we show that under very mild conditions of curvature of a function, adaptive sampling techniques achieve an approximation arbitrarily close to 1/2 while maintaining their low adaptivity. Furthermore, we show that the approximation ratio approaches 1 in direct relationship to a homogeneity property of the submodular function. In addition, we conduct experiments on real data sets in which the curvature and homogeneity properties can be easily manipulated and demonstrate the relationship between approximation and curvature, as well as the effectiveness of adaptive sampling in practice.