Greedy Minimization of Weakly Supermodular Set Functions

Abstract

This paper defines weak-$\alpha$-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^{\ast }$ be the optimal set of cardinality $k$ that minimizes $f$ and let $S_0$ be an initial solution such that $f(S_0)/f(S^{\ast })\le \rho$. Then, a greedy extension $S\supset S_0$ of size $|S|\le |S_0|+\lceil \alpha k\ln (\rho /\epsilon )\rceil$ yields $f(S)/f(S^{\ast })\le 1+\epsilon$. As example usages of this framework we give new bicriteria results for $k$-means, sparse regression, and columns subset selection.