coreset selection

A coreset is a small, cleverly weighted subset of your data chosen so that training on it gives almost the same model as training on everything. The picture is a study guide: instead of re-reading the whole textbook, you keep a handful of representative pages whose weighted total behaves like the full book for the purpose of passing the exam. The promise is dramatic compute savings with a provable bound on how much you lose.

The classical guarantee is geometric: pick a subset and weights so that the weighted sum of per-example loss gradients matches the full-dataset gradient to within ε for every parameter in a region, so gradient descent on the coreset tracks gradient descent on the full set. Methods include importance sampling by gradient norm or sensitivity, greedy submodular maximization for coverage, k-center clustering in feature space, and gradient-matching objectives like CRAIG and GradMatch. The weights matter as much as the selection — they correct the sampling bias so the small set is an unbiased, low-variance estimator of the full objective.

Coresets shine for repeated training (hyperparameter search, continual learning) and for active learning budgets. The caveat is that the bound is local to a model class and region; under non-convex deep nets and distribution shift the guarantee weakens, and a coreset tuned for one architecture may not transfer to another.