Guarantees for Greedy Maximization of Non-submodular Functions with Applications

Andrew An Bian, Joachim M. Buhmann, Andreas Krause, Sebastian Tschiatschek
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:498-507, 2017.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-bian17a, title = {Guarantees for Greedy Maximization of Non-submodular Functions with Applications}, author = {Andrew An Bian and Joachim M. Buhmann and Andreas Krause and Sebastian Tschiatschek}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {498--507}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/bian17a/bian17a.pdf}, url = {https://proceedings.mlr.press/v70/bian17a.html}, 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.} }
Endnote
%0 Conference Paper %T Guarantees for Greedy Maximization of Non-submodular Functions with Applications %A Andrew An Bian %A Joachim M. Buhmann %A Andreas Krause %A Sebastian Tschiatschek %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-bian17a %I PMLR %P 498--507 %U https://proceedings.mlr.press/v70/bian17a.html %V 70 %X 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.
APA
Bian, A.A., Buhmann, J.M., Krause, A. & Tschiatschek, S.. (2017). Guarantees for Greedy Maximization of Non-submodular Functions with Applications. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:498-507 Available from https://proceedings.mlr.press/v70/bian17a.html.

Related Material