  Deep learning has yielded extraordinary results in vision and natural
language processing, but this achievement comes at a cost. Most models require
enormous resources during training, both in terms of computation and in human
labeling effort. We show that we can identify informative and diverse subsets
of data that lead to deep learning models with similar performance as the ones
trained with the original dataset. Prior methods have exploited diversity and
uncertainty in submodular objective functions for choosing subsets. In addition
to these measures, we show that balancing constraints on predicted class labels
and decision boundaries are beneficial. We propose a novel formulation of these
constraints using matroids, an algebraic structure that generalizes linear
independence in vector spaces, and present an efficient greedy algorithm with
constant approximation guarantees. We outperform competing baselines on
standard classification datasets such as CIFAR-10, CIFAR-100, ImageNet, as well
as long-tailed datasets such as CIFAR-100-LT.
