GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility

This work studies a novel subset selection problem called max-min diversification with monotone submodular utility (textsfMDMS), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of textsfMDMS is to maximize f(S) = g(S) + λ · textttdiv(S) subject to a cardinality constraint |S| ≤ k, where g(S) is a monotone submodular function and textttdiv(S) = minu,v ∈ S : u ne v dist(u,v) is the max-min diversity objective. We propose the textttGIST algorithm, which gives a frac12-approximation guarantee for textsfMDMS by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of 0.5584. Finally, we show in our empirical study that textttGIST outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet.