  One-shot coreset selection aims to select a representative subset of the
training data, given a pruning rate, that can later be used to train future
models while retaining high accuracy. State-of-the-art coreset selection
methods pick the highest importance examples based on an importance metric and
are found to perform well at low pruning rates. However, at high pruning rates,
they suffer from a catastrophic accuracy drop, performing worse than even
random sampling. This paper explores the reasons behind this accuracy drop both
theoretically and empirically. We first propose a novel metric to measure the
coverage of a dataset on a specific distribution by extending the classical
geometric set cover problem to a distribution cover problem. This metric helps
explain why coresets selected by SOTA methods at high pruning rates perform
poorly compared to random sampling because of worse data coverage. We then
propose a novel one-shot coreset selection method, Coverage-centric Coreset
Selection (CCS), that jointly considers overall data coverage upon a
distribution as well as the importance of each example. We evaluate CCS on five
datasets and show that, at high pruning rates (e.g., 90%), it achieves
significantly better accuracy than previous SOTA methods (e.g., at least 19.56%
higher on CIFAR10) as well as random selection (e.g., 7.04% higher on CIFAR10)
and comparable accuracy at low pruning rates. We make our code publicly
available at
https://github.com/haizhongzheng/Coverage-centric-coreset-selection.
