GIST: Greedy Independent Set Thresholding for Diverse Data Summarization

We propose a novel subset selection task called min-distance diverse data summarization (MDDS), which has a wide variety of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal is to maximize an objective that combines the total utility of the points and a diversity term that captures the minimum distance between any pair of selected points, subject to the constraint |S| ≤ k. For example, the points may correspond to training examples in a data sampling problem, e.g., learned embeddings of images extracted from a deep neural network. This work presents the GIST algorithm, which achieves a 2/3-approximation guarantee for MDDS by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove a complementary (2/3+ε)-hardness of approximation, for any ε > 0. Finally, we provide an empirical study that demonstrates GIST outperforms existing methods for MDDS on synthetic data, and also for a real-world image classification experiment the studies single-shot subset selection for ImageNet.