Guarantees for Greedy Maximization of Nonsubmodular Functions with Applications
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:498507, 2017.
Abstract
We investigate the performance of the standard Greedy algorithm for cardinality constrained maximization of nonsubmodular nondecreasing set functions. While there are strong theoretical guarantees on the performance of Greedy for maximizing submodular functions, there are few guarantees for nonsubmodular ones. However, Greedy enjoys strong empirical performance for many important nonsubmodular functions, e.g., the Bayesian Aoptimality objective in experimental design. We prove theoretical guarantees supporting the empirical performance. Our guarantees are characterized by a combination of the (generalized) curvature $\alpha$ and the submodularity ratio $\gamma$. In particular, we prove that Greedy enjoys a tight approximation guarantee of $\frac{1}{\alpha}(1 e^{\gamma\alpha})$ for cardinality constrained maximization. In addition, we bound the submodularity ratio and curvature for several important realworld objectives, including the Bayesian Aoptimality objective, the determinantal function of a square submatrix and certain linear programs with combinatorial constraints. We experimentally validate our theoretical findings for both synthetic and realworld applications.
Related Material


