Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap

In this paper, we study the problem of textitconstrained and textitstochastic continuous submodular maximization. Even though the objective function is not concave (nor convex) and is defined in terms of an expectation, we develop a variant of the conditional gradient method, called alg, which achieves a textittight approximation guarantee. More precisely, for a monotone and continuous DR-submodular function and subject to a textitgeneral convex body constraint, we prove that alg achieves a [(1-1/e)OPT -eps] guarantee (in expectation) with O(1/eps3) stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. By using stochastic continuous optimization as an interface, we also provide the first (1-1/e) tight approximation guarantee for maximizing a textitmonotone but stochastic submodular textitset function subject to a general matroid constraint.