Greedy Minimization of Weakly Supermodular Set Functions

This paper defines weak-α-supermodularity for set functions. Many optimization objectives in machine learning and data mining seek to minimize such functions under cardinality constrains. We prove that such problems benefit from a greedy extension phase. Explicitly, let S^* be the optimal set of cardinality k that minimizes f and let S0 be an initial solution such that f(S0)/f(S^*) ≤ ρ. Then, a greedy extension S supset S0 of size |S| ≤ |S0| + lceil α k ln(ρ/varepsilon) rceil yields f(S)/f(S^*) ≤ 1+varepsilon. As example usages of this framework we give new bicriteria results for k-means, sparse regression, and columns subset selection.