A Unified Approach to Submodular Maximization Under Noise

We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of an exact value oracle. Similar to prior work [13, 16] , we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer [13] design a (1 -1/e)-approximation algorithm for monotone submodular maximization subject to a cardinality constraint and Huang et al. [16] design a (1 -1/e)/2-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a (1 -1/e)-approximation (resp. 1/e-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a 1/2-approximation for unconstrained (non-monotone) submodular maximization under noise.