A Weighted K-Center Algorithm for Data Subset Selection
Srikumar Ramalingam Pranjal Awasthi Sanjiv Kumar
The success of deep learning hinges on enormous data and large models, which
require labor-intensive annotations and heavy computation costs. Subset
selection is a fundamental problem that can play a key role in identifying
smaller portions of the training data, which can then be used to produce
similar models as the ones trained with full data. Two prior methods are shown
to achieve impressive results: (1) margin sampling that focuses on selecting
points with high uncertainty, and (2) core-sets or clustering methods such as
k-center for informative and diverse subsets. We are not aware of any work that
combines these methods in a principled manner. To this end, we develop a novel
and efficient factor 3-approximation algorithm to compute subsets based on the
weighted sum of both k-center and uncertainty sampling objective functions. To
handle large datasets, we show a parallel algorithm to run on multiple machines
with approximation guarantees. The proposed algorithm achieves similar or
better performance compared to other strong baselines on vision datasets such
as CIFAR-10, CIFAR-100, and ImageNet.