Abstract

In this paper, we develop Stochastic Continuous Greedy++ (SCG++), the first efficient variant of a conditional gradient method for maximizing a continuous submodular function subject to a convex constraint. Concretely, for a monotone and continuous DR-submodular function, SCG++ achieves a tight [(1 — 1/)OPT— ] solution while using O(1/ ) stochastic gradients and O(1/) calls to the linear optimization oracle. The best previously known algorithms either achieve a suboptimalsolution with stochastic gradients or the tight [(1 — 1/)OPT — ] solution with suboptimal stochastic gradients. We further provide an information-theoretic lower bound to showcase the necessity of stochastic oracle queries in order to achieve [(1 — 1/)OPT — ] for monotone and DR-submodular functions. This result shows that our proposed SCG++ enjoys optimality in terms of both approximation guarantee, i.e., (1—1/) approximation factor, and stochastic gradient evaluations, i.e., calls to the stochastic oracle. By using stochastic continuous optimization as an interface, we also show that it is possible to obtain the tight approximation guarantee for maximizing a monotone but stochastic submodular set function subject to a general matroid constraint after at most calls to the stochastic function value, where n is the number of elements in the ground set.