Guarantees for Greedy Maximization of Non-submodular Functions with Applications
Yatao (An) Bian · Joachim Buhmann · Andreas Krause · Sebastian Tschiatschek

Wed Aug 9th 06:30 -- 10:00 PM @ Gallery #72

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.

Author Information

Yatao (An) Bian (ETH Zurich)
Joachim Buhmann (ETH Zurich)
Andreas Krause (ETH Zurich)
Sebastian Tschiatschek (ETH)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors