by , , ,
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 α and the submodularity ratio γ. In particular, we prove that GREEDY enjoys a tight approximation guarantee of $1/\alpha(1 − \exp{−\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.
Reference:
Guarantees for Greedy Maximization of Non-submodular Functions with Applications A. A. Bian, J. Buhmann, A. Krause, S. TschiatschekIn Proc. International Conference on Machine Learning (ICML), 2017
Bibtex Entry:
@inproceedings{bian17guarantees)$ 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 = {Andrew An Bian and Joachim Buhmann and Andreas Krause and Sebastian Tschiatschek},
	Booktitle = {Proc. International Conference on Machine Learning (ICML)},
	Month = {August},
	Title = {Guarantees for Greedy Maximization of Non-submodular Functions with Applications},
	Year = {2017}}