A Unified Approach to Submodular Maximization Under Noise
This work addresses a key challenge in optimization under uncertainty for researchers and practitioners in machine learning and operations research, offering a general framework that improves upon prior specific results.
The paper tackles the problem of maximizing submodular functions with noisy value oracles by introducing a meta-algorithm that transforms robust exact algorithms into noisy-setting algorithms, achieving approximation guarantees such as (1-1/e) for monotone functions under matroid constraints and 1/2 for unconstrained non-monotone functions.
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, 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 (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) 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.