Title: Guarantees for Greedy Maximization of Non-submodular Functions with Applications,
Abstract: We investigate the performance of the standard Greedy algorithm for
cardinality constrained maximization of non-submodular nondecreasing set
functions. While there are strong theoretical guarantees on the performance of
Greedy for maximizing submodular functions, there are few guarantees for
non-submodular ones. However, Greedy enjoys strong empirical performance for
many important non-submodular functions, e.g., the Bayesian A-optimality
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 real-world objectives, including the Bayesian A-optimality
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 real-world applications.