Title: Black Box Submodular Maximization: Discrete and Continuous Settings

Authors: Lin Chen, Mingrui Zhang, Hamed Hassani, Amin Karbasi:


In this paper, we consider the problem of black box continuous submodular maximization where we only have access to the function values and no information about the derivatives is provided. For a monotone and continuous DR-submodular function, and subject to a bounded convex body constraint, we propose Black-box Continuous Greedy, a derivative-free algorithm that provably achieves the tight [(1−1/e)OPT−ϵ] approximation guarantee with $O(d/ϵ^3)$ function evaluations. We then extend our result to the stochastic setting where function values are subject to stochastic zero-mean noise. It is through this stochastic generalization that we revisit the discrete submodular maximization problem and use the multi-linear extension as a bridge between discrete and continuous settings. Finally, we extensively evaluate the performance of our algorithm on continuous and discrete submodular objective functions using both synthetic and real data.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale