Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper reformulates dataset pruning as a variance minimization problem, deriving unbiased subset selection criteria from first principles without relying on geometric assumptions or labels. By characterizing unbiased selection as a high-dimensional polytope and minimizing sampling variance as a linear objective, the authors develop an efficient vertex walk algorithm. This label-free, training-free approach matches or exceeds uniform sampling and outperforms competing methods, particularly at low budgets, while also offering benefits for mini-batch diversity.
Unbiased dataset pruning can be framed as a linear program, enabling efficient, label-free subset selection that outperforms geometric methods at small budgets.
Dataset pruning reduces a large training set to a representative subset while preserving model performance. Existing geometry-based methods typically assume that nearby points in embedding space share similar properties. Rather than imposing this assumption, we derive geometric selection criteria by reformulating unbiased subset selection as a variance minimization problem. Unbiasedness ensures that unweighted subset averages recover full-dataset averages in expectation, including losses and gradients at fixed model parameters. Specifically, we characterize a family of unbiased subset selection algorithms as a high-dimensional polytope. In this context, minimizing the expected sampling variance is a linear objective. Differences in sampling variance, averaged over rigid motions, admit closed-form pairwise expressions. Because the polytope has high dimension, directly applying standard linear programming is impractical. We instead use these expressions to construct an efficient vertex walk that optimizes an approximation of the variance objective while preserving unbiasedness, yielding a method that requires neither labels nor model training during selection. Across CIFAR-10, MNIST, and CelebA benchmarks, our method matches or exceeds uniform sampling in mean test accuracy at every evaluated budget and outperforms competing geometric methods in several settings, particularly at small selection budgets. Beyond dataset pruning, the same framework reduces stochastic-gradient variance by increasing diversity within mini-batches while keeping the batch size unchanged.