Black Box Submodular Maximization: Discrete and Continuous Settings

Abstract

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-\epsilon ]$ approximation guarantee with $O(d/{\epsilon }^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.

Accepted to AISTATS 2020. First two authors contributed equally to this work

References in corpus (15)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Cooperative Game Theory Approaches for Network Partitioning
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Influence Maximization in Continuous Time Diffusion Networks
• Near-Optimally Teaching the Crowd to Classify
• Structured sparsity-inducing norms through submodular functions
• Stochastic Zeroth-order Optimization in High Dimensions
• Online Continuous Submodular Maximization
• How to be Fair and Diverse?
• Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
• Causal Markov condition for submodular information measures
• Towards Gradient Free and Projection Free Stochastic Optimization
• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Categorical Feature Compression via Submodular Optimization

Cited by in corpus (1)

• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization