We propose a novel subset selection task called min-distance diverse data summarization ($\textsf{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| \le 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 $\texttt{GIST}$ algorithm, which achieves a $\frac{2}{3}$-approximation guarantee for $\textsf{MDDS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove a complementary $(\frac{2}{3}+\varepsilon)$-hardness of approximation, for any $\varepsilon > 0$. Finally, we provide an empirical study that demonstrates $\texttt{GIST}$ outperforms existing methods for $\textsf{MDDS}$ on synthetic data, and also for a real-world image classification experiment the studies single-shot subset selection for ImageNet.

我们提出了一种新颖的子集选择任务，称为最小距离多样化数据汇总（MDDS），它在机器学习中有广泛的应用，例如数据采样和特征选择。我们介绍了GIST算法，它通过将一系列最大独立集问题近似为双准则贪婪算法来实现MDDS的2/3近似保证。我们还证明了对于任意ε>0，存在一个补充的（2/3+ε）-近似难度。最后，我们通过实证研究证明了GIST在合成数据上优于现有方法，并且对于一个真实的图像分类实验，GIST用于ImageNet的单次子集选择也表现出色。

GIST：贪婪独立集合阈值用于多样数据摘要