GIST: Greedy Independent Set Thresholding for Diverse Data Summarization
<|reference_start|>GIST: Greedy Independent Set Thresholding for Diverse Data Summarization: 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.<|reference_end|>
@article{fahrbach2024gist:,
    title={GIST: Greedy Independent Set Thresholding for Diverse Data Summarization},
    author={Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam, Sara
  Ahmadian, Gui Citovsky, Giulia DeSalvo},
    journal={arXiv preprint arXiv:2405.18754},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.18754},
    primaryClass={cs.DS cs.LG}
}