论文标题
在噪声下有效的下二次优化：本地搜索是可靠的
Efficient Submodular Optimization under Noise: Local Search is Robust
论文作者
论文摘要
由于其广泛的应用范围，已经对单调性量最大化的问题进行了广泛的研究。但是，在某些情况下，由于不确定的性质或评估中涉及的错误，只能以扭曲或嘈杂的形式访问目标函数。本文考虑了[Hassidim等，2017]引入的嘈杂的甲骨文，从而考虑了受约束的单调下二酮最大化的问题。对于基质性约束，我们提出了一种算法，以实现近距离的$ \ weft（1- \ frac {1} {e} {e} -o（\ varepsilon）\ right）$ - 近似保证（对于任意$ \ varepsilon> 0 $），只有queries of queries of query of query of query of query of query of query of query of query to query of query of query to query， [Singer等，2018]。对于一般的Matroid约束，我们在存在噪声的情况下显示了第一个常数近似算法。我们的主要方法是设计一个新型的本地搜索框架，该框架可以处理噪声的效果并构建某些平滑替代功能以减少噪声。
The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by [Hassidim et al., 2017]. For a cardinality constraint, we propose an algorithm achieving a near-optimal $\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation guarantee (for arbitrary $\varepsilon > 0$) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of [Singer et al., 2018]. For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction.
