Guarantees for Greedy Maximization of Non-submodular Functions with Applications

By Yatao Bian, Joachim M. Buhmann, Andreas Krause, Sebastian Tschiatschek. 2017

267 citations recorded by the source corpus.

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 sub-modularity ratio γ. In particular, we prove that GREEDY enjoys a tight approximation guarantee of 1/α (1 - e-γα) for cardinality constrained maximization. In addition, we bound the submod-ularity 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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, background): “Relaxed notions of submodularity/supermodularity, called weak DR-submodularity/supermodularity , were introduced in [Lehmann et al., 2006] and [Bian et al., 2017], respectively.”
Restricted Strong Convexity Implies Weak Submodularity (2016, background): “In [6], the authors show tight bounds for maximizing cardinality constrained, weakly submodular set functions that also have bounded curvature.”
Fast Parallel Algorithms for Feature Selection (2019, methodology): “In a series of recent works, both feature selection (selecting k out of n features) and experimental design (choosing k out of n samples) were shown to be weakly submodular [10, 13, 6].”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, background): “Bian et al. [2017] showed that g is γ-weakly submodular, providing a lower bound for γ in the case where Σ = βI.”