We consider the problem of maximizing monotone submodular functions under noise, which to the best of our knowledge has not been studied in the past. There has been a great deal of work on optimization of submodular functions under various constraints, with many algorithms that provide desirable approximation guarantees. However, in many applications we do not have access to the submodular function we aim to optimize, but rather to some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a monotone submodular function under cardinality constraints when given access to a noisy oracle of the function. We show that: For a cardinality constraint $k \geq 2$, there is an approximation algorithm whose approximation ratio is arbitrarily close to $1-1/e$; For $k=1$ there is an approximation algorithm whose approximation ratio is arbitrarily close to $1/2$ in expectation. No randomized algorithm can obtain an approximation ratio in expectation better than $1/2+O(1/\sqrt n)$ and $(2k - 1)/2k + O(1/\sqrt{n})$ for general $k$; If the noise is adversarial, no non-trivial approximation guarantee can be obtained.

本文考虑在噪声下最大化单调子模函数，探讨在噪声和误差存在的情况下，是否能获得算法的可证明保证，结论是对于基数约束k>=2的函数，有一个近似算法，其近似比例任意接近1-1/e;对于基数约束k=1，有一种算法，其近似比率任意接近于1/2。没有随机算法可以获得比1/2+o(1)更好的近似度;如果噪声是对抗性的，则不能获得任何非平凡的近似保证。

噪音下的次模优化