Greedy Guarantees for Non-submodular Function Maximization Under Independent System Constraint with Applications

We study the problems of maximizing a monotone non-submodular function subject to two types of constraints, either an independent system constraint or ap-matroidconstraint. These problems often occur in the context of combinatorial optimization, operations research, economics and especially, machine learning and data science. Using the generalized curvature alpha and the submodularity ratio gamma or the diminishingreturns ratio xi, we analyze the performances of the widely used greedy algorithm, which yields theoretical approximation guarantees of 1/alpha[1-(1-alpha gamma/K)(k)]and xi/p+alpha xi for the two types of constraints, respectively, where k ,K are, respectively, the min-imum and maximum cardinalities of a maximal independent set in the independent system, and p is the minimum number of matroids such that the independent sys-tem can be expressed as the intersection of p matroids. When the constraint is acardinality one, our result maintains the same approximation ratio as that in Bian etal. (Proceedings of the 34th international conference on machine learning, pp 498-507, 2017); however, the proof is much simpler owning to the new definition of the greedy curvature. In the case of a single matroid constraint, our result is competitive compared with the existing ones in Chen et al. (Proceedings of the 35th international conference on machine learning, pp 804-813, 2018) and Gatmiry and Rodriguez (Non-submodular function maximization subject to a matroid constraint, with applications,2018.arXiv:1811.07863v4). In addition, we bound the generalized curvature, thesubmodularity ratio and the diminishing returns ratio for several important real-worldapplications. Computational experiments are also provided supporting our analyses.