Optimal approximation for unconstrained non-submodular minimization
arXiv:1905.12145
Abstract
Submodular function minimization is well studied, and existing algorithms solve it exactly or up to arbitrary accuracy. However, in many applications, such as structured sparse learning or batch Bayesian optimization, the objective function is not exactly submodular, but close. In this case, no theoretical guarantees exist. Indeed, submodular minimization algorithms rely on intricate connections between submodularity and convexity. We show how these relations can be extended to obtain approximation guarantees for minimizing non-submodular functions, characterized by how close the function is to submodular. We also extend this result to noisy function evaluations. Our approximation results are the first for minimizing non-submodular functions, and are optimal, as established by our matching lower bound.
References in corpus (11)
- Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
- Batch Bayesian Optimization via Local Penalization
- Guarantees for Greedy Maximization of Non-submodular Functions with Applications
- Maximization of Approximately Submodular Functions
- Structured sparsity-inducing norms through submodular functions
- Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
- Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
- Submodular Functions: Extensions, Distributions, and Algorithms. A Survey
- Robust Maximization of Non-Submodular Objectives
- Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
- On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness